Rotation Dilemma

upobir The Tough Winter Spar, 20...
Limits 2.5s, 512 MB

Akash has two favorite convex polygons AA and BB. 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 PP and rotate the polygon BB, DD degrees counter-clockwise with respect to PP. After the rotation, you are hoping that the new polygon BB' and AA will become one connected region, and this connected region will be Akash's new favorite polygon. Formally speaking, you are hoping that AA and BB' will have a non-empty intersection.

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


In the first line number of test cases TT (0<T50 < T \leq 5) is given. Each test case starts with a line containing DD (0<D<3600 < D < 360). Next, two polygons AA and BB will be described. For each polygon, the first line contains the number of points nn (3n1053 \leq n \leq 10^5), next nn lines will contain coordinates (x,y)(x, y) (x,y107|x|, |y| \le 10^7) 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 180180 degrees but not more.


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 10610^{-6}. That is, if your answer is PP and jury's answer is QQ, your answer will be considered correct if PQmax(1,Q)<106\frac{|P-Q|}{max(1, Q)} < 10^{-6}.


0 0 
2 0
2 2
0 2
3 3
5 3
5 5
3 5

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.


Login to submit.


80% Solution Ratio
AnachorEarliest, Dec '19
dragoonFastest, 0.2s
tmwilliamlin168Lightest, 9.1 MB
tmwilliamlin168Shortest, 1682B
Toph uses cookies. By continuing you agree to our Cookie Policy.