Problem Description

Given two convex polygons $S$ and $T$ on a 2D plane.

$S$ consists of $N$ vertices, with the coordinates of the vertices being $(a_1, b_1), \dots, (a_N, b_N)$ in counterclockwise order.
$T$ consists of $M$ vertices, with the coordinates of the vertices being $(c_1, d_1), \dots, (c_M, d_M)$ in counterclockwise order.

Calculate the area of the intersection of $S$ and $T$.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$ $c_1$ $d_1$ $\vdots$ $c_M$ $d_M$

Output Format

Output the answer. The answer will be considered correct if the absolute or relative error is within $10^{-6}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2.00000000000000000000

Sample Input #2

3 3
0 0
3 0
0 3
3 3
0 3
3 0

Sample Output #2

0.00000000000000000000

Sample Input #3

3 3
1 3
0 2
2 0
3 1
2 3
0 1

Sample Output #3

0.79166666666666662966

Notes/Hints

Constraints

• $3 \leq N, M \leq 10^3$
• $0 \leq a_i, b_i \leq 3 \times 10^4 \ (1 \leq i \leq N)$
• $0 \leq c_i, d_i \leq 3 \times 10^4 \ (1 \leq i \leq M)$
• $(a_1, b_1), \dots, (a_N, b_N)$ are the vertices of $S$ listed in counterclockwise order.
• $(c_1, d_1), \dots, (c_M, d_M)$ are the vertices of $T$ listed in counterclockwise order.
• All inputs are integers.

Sample Explanation 1

The intersection of $S$ and $T$ is the gray area in the figure below, and its area is $2$.

见题面 Input 部分

见题面 Output 部分