402933: GYM100952 J Polygons Intersection

We will not waste your time, it is a straightforward problem. Given multiple polygons, calculate the area of their intersection. For simplicity, there will be exactly 2 polygons both of them are convex, given in the counterclockwise order and have non-zero areas. Furthermore, in one polygon a vertex won't be on the sides of the other one. The figure below demonstrates the first test case.

The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  20). each test case contains two integers (3  ≤  N, M  ≤  40) Then a line contains N pairs of integers x_i, y_i (-1000  ≤  x_i, y_i  ≤  1000) coordinates of the ith vertex of polygon A, followed by a line contains M pairs of integers x_j, y_j (-1000  ≤  x_j, y_j  ≤  1000) coordinates of the jth vertex of polygon B. The coordinates are separated by a single space.

For each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places.

2
5 3
0 3 1 1 3 1 3 5 1 5
1 3 5 3 3 6
3 3
-1 -1 -2 -1 -1 -2
1 1 2 1 1 2

2.6667
0.0000