On this day, Sonetto purchased her first spacecraft (which can be considered as a convex polygon) and
eagerly began to operate it. This spacecraft had a touch screen interface where the user could click on a
position, and the spacecraft would instantly teleport to that location. However, since Sonetto bought a
smuggled spacecraft, after Sonetto clicks on a location, the system randomly selects a point within a circle
centered at Sonetto’s clicked position with a radius of R, and the spacecraft teleport to that point.On this
day, there was a Mr.Cookie’s spacecraft parked in the vicinity, which can also be seen as a convex polygon.
Now, given the position where Sonetto clicked on the screen, you are asked to calculate the probability
of Sonetto0
s spacecraft colliding with Mr.Cookie’s spacecraft parked in the area.
Because the space where Sonetto is located is a rather mysterious space, Sonetto’s spacecraft may initially
intersect with Mr.Cookie0
s spacecraft. However, we don’t need to be concerned about Sonetto0
s initial
position. We only need to focus on whether the position of her spacecraft after the instant teleportation
will collide with Mr.Cookie’s spacecraft.
To be more specific, you are given two convex polygons A and B, and a circle P (centered at point X with
radius R). You need to determine the probability of randomly selecting a point S within the circle P, such
that when the convex polygon A moves along the vector OS~ (O is the origin point (0,0)), it transforms
into a new convex polygon A0
, and A0
intersects with B (intersection implies that there exists a point w
such that w ∈ A0 and w ∈ B).
输入格式
The input consists of multiple test cases. The first line contains a single integer t(1 ≤ t ≤ 1200) — the
number of test cases. Description of the test cases follows.
The second line contains a integer n (3 ≤ n ≤ 30000), denoting the number of vertices of the convex
polygons A.
Then follows n lines, each line contains two integers xi
, yi (−108 ≤ xi
, yi ≤ 108 ), denoting the ith point
of the convex polygon A. The points are given in counter-clockwise order.
The next line contains a integer m (3 ≤ m ≤ 30000), denoting the number of vertices of the convex
polygons B.
Then follows m lines, each line contains two integers xi
, yi (−108 ≤ xi
, yi ≤ 108 ), denoting the ith point
of the convex polygon B. The points are given in counter-clockwise order.
The last line contains three integers x,y and r,denoting the position of the center of the circle P and the
radius of the circle. (−108 ≤ xi
, yi ≤ 108 , 1 ≤ r ≤ 108 )
The data guarantees that the sum of n will not exceed 2 · 105
The data guarantees that the sum of m will not exceed 2 · 105
输出格式
For each test case print a single floating-point number denoting the probability of A' intersects with
B.(keep 4 decimal places)