Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rotation Dilemma

By upobir · Limits 2.5s, 512 MB

Akash has two favorite convex polygons $A$ and $B$. But one of his new year resolution for 2020 is to have only one favorite polygon (not necessarily convex). So, he is in a dilemma and has given you the task to somehow merge these two polygons. Having received such a task, the first thing that came to your mind is to choose a point $P$ and rotate the polygon $B$, $D$ degrees counter-clockwise with respect to $P$. After the rotation, you are hoping that the new polygon $B'$ and $A$ will become one connected region, and this connected region will be Akash’s new favorite polygon. Formally speaking, you are hoping that $A$ and $B'$ will have a non-empty intersection.

Of course, choosing any random $P$ will not get you this result. Still, there are many valid choices for $P$, in fact, all such choices form a bounded measurable shape (locus as a geometer would call it). So before choosing a $P$ and rotating the polygon, you decide to find the area of this shape/locus.

Input

In the first line number of test cases $T$ is given. Each test case starts with a line containing $D$. Next, two polygons $A$ and $B$ will be described. For each polygon, the first line contains the number of points $n$, next $n$ lines will contain coordinates $x, y$ of the points. All input numbers will be integers. The points will be in counter-clockwise order. Note that the polygons are not necessarily strictly convex i.e. internal angles can be $180$ degrees but not more.

$0 < T \leq 5$
$0 < D < 360$
$3 \leq n \leq 10^5$
$|x|, |y| <= 10^7$

Output

For each test case, output the area of the locus of P in a single line. Your answer will be considered correct if the relative or absolute difference is less than $10^{-6}$. That is, if your answer is $P$ and jury’s answer is $Q$, your answer will be considered correct if $\frac{|P-Q|}{max(1, Q)} < 10^{-6}$

Sample

InputOutput
1
90
4
0 0 
2 0
2 2
0 2
4
3 3
5 3
5 5
3 5
8.00000000

In the pictures below, the blue square is polygon A, red squares are B and B’. The green shape is the locus of P. note that when P is inside it, B’ and A have a non-empty intersection. But when P is outside the green area, B’ and A do not intersect.

Discussion

Statistics


86% Solution Ratio

AnachorEarliest, 1M ago

dragoonFastest, 0.2s

tmwilliamlin168Lightest, 9.1 MB

tmwilliamlin168Shortest, 1682B

Submit

Login to submit

Related Contests

The Tough Winter Spar, 2019 Ended at 2020-01-04 12:00:00 +0000 UTC