# Practice on Toph

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

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.

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$`

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}$`

Input | Output |
---|---|

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.

86% Solution Ratio

AnachorEarliest,

dragoonFastest, 0.2s

tmwilliamlin168Lightest, 9.1 MB

tmwilliamlin168Shortest, 1682B

Login to submit

Let R be the function that rotates a point D degrees counter clockwise w.r.t to origin O. then if p...