Amazing spacecraft

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 $Sonetto'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.Cookie's$ spacecraft. However, we don't need to be concerned about $Sonetto'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 $\vec{OS}$($O$ is the origin point (0,0)), it transforms into a new convex polygon $A'$, and $A'$ intersects with $B$ (intersection implies that there exists a point $w$ such that $w \in A'$ and $w \in 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 $x_i$, $y_i$ ($-10^8\le x_i,\ y_i\le 10^8$), denoting the $i$th 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 $x_i$, $y_i$ ($-10^8\le x_i,\ y_i\le 10^8$), denoting the $i$th 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. ($-10^8\le x_i,\ y_i\le 10^8,0\le r \le 10^8$)

The data guarantees that the sum of $n$ will not exceed $2\cdot 10^5$

The data guarantees that the sum of $m$ will not exceed $2\cdot 10^5$

For each test case print a single floating-point number denoting the probability of $A'$ intersects with $B$.(keep 4 decimal places)

2
5
0 -2
4 -1
4 0
1 1
0 0
4
0 -2
3 -1
2 1
1 0
-2 -2 3
4
-2 0
-1 -2
1 2
-1 2
3
2 0
5 1
3 1
1 -3 4

0.5247
0.1185

2023“钉耙编程”中国大学生算法设计超级联赛（1）