G. Collision Damage
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a 2D physics-based video game, two characters $$$P$$$ and $$$Q$$$ move across the battlefield. Each character is represented by a convex polygon that serves as its collision box. When the two collision boxes overlap, the game calculates the area of their intersection as the collision damage.

However, due to unpredictable wind currents in the arena, character $$$Q$$$ can be displaced by an arbitrary translation vector $$$\mathbf{t} = (t_x, t_y)$$$, but it cannot rotate or flip. You need to calculate the expected collision damage when $$$Q$$$ is uniformly and randomly placed such that it actually collides with $$$P$$$, i.e., their intersection has a positive area.

More formally, define $$$f(\mathbf{t})$$$ as the area of the intersection between the polygon representing character $$$P$$$ and the polygon representing character $$$Q$$$ after being translated along $$$\mathbf{t}$$$. Let $$$D \subseteq \mathbb{R}^2$$$ be the set of all translation vectors $$$\mathbf{t}$$$ for which $$$f(\mathbf{t}) \gt 0$$$. It can be shown that $$$D$$$ has a positive area, denoted by $$$|D|$$$. You need to calculate $$$\frac{1}{|D|} \iint\limits_{D} f(\mathbf{t}) \, d\mathbf{t}$$$.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 300$$$), denoting the number of test cases. For each test case:

  • The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n, m \le 1\,000$$$), denoting the numbers of vertices of the two convex polygons, respectively.
  • Then $$$n$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$-10^4 \le x,y \le 10^4$$$), giving the vertex coordinates $$$(x, y)$$$ of the polygon representing character $$$P$$$.
  • Then $$$m$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$-10^4 \le x,y \le 10^4$$$), giving the vertex coordinates $$$(x, y)$$$ of the polygon representing character $$$Q$$$.
  • It is guaranteed that the vertices of a convex polygon are given in counter-clockwise order, and no three of them are collinear.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$1\,000$$$.

Output

For each test case, output a line containing a real number, representing the expected collision damage.

Your answer is acceptable if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, and your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$.

Example
Input
2
3 3
0 0
1 0
0 1
0 0
1 0
0 1
3 3
0 0
1 0
0 1
0 1
1 0
1 1
Output
0.083333333333
0.125000000000