407360: GYM102770 H Huge Clouds

It's a starry night and DreamGrid is counting stars. Unfortunately, it becomes cloudy and many stars are hidden from view. DreamGrid wants to go out of the shadow and find a place where at least one star can be seen. He wants to know the total area of the shadow first.

There are $$$n$$$ stars and $$$m$$$ clouds in the sky. Formally, each star is represented by a point $$$(x_i, y_i) \ (1 \le i \le n)$$$ in a two-dimensional plane. The $$$i$$$-th ($$$1 \le i \le m$$$) cloud is represented by a segment $$$(u_{i1},v_{i1})-(u_{i2},v_{i2})$$$, where $$$(u_{i1},v_{i1})$$$ and $$$(u_{i2},v_{i2})$$$ are the two endpoints of the segment.

For a viewpoint $$$(x, 0)$$$ on the x-axis, DreamGrid considers it to be in shadow if none of the stars can be seen there. A star can be seen at a viewpoint if the segment connecting the viewpoint and the star doesn't intersect with any cloud (including the endpoints of a cloud). Note that if a cloud (including its endpoints) goes through a star, the star can't be seen anywhere.

It's tiring to go through the whole x-axis and calculate the total shadow area. Can you tell DreamGrid the total area (length) covered by shadow on the x-axis?

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \le T \le 500)$$$, the number of cases.

For each case, the first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 500$$$), the number of stars and clouds. The following $$$n$$$ lines describe the positions of the stars. The $$$i$$$-th ($$$1 \le i \le n$$$) line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \le x_i \le 10^4$$$, $$$1 \le y_i \le 10^4$$$), the position of the $$$i$$$-th star. The following $$$m$$$ lines describe the positions of the clouds. The $$$i$$$-th ($$$1 \le i \le m$$$) line contains four integers $$$u_{i1},v_{i1},u_{i2},v_{i2}$$$ ($$$-10^4 \le u_{i1}, u_{i2} \le 10^4$$$, $$$1 \le v_{i1},v_{i2} \le 10^4, (u_{i1},v_{i1}) \ne (u_{i2},v_{i2})$$$), the positions of the endpoints of the $$$i$$$-th cloud.

It's guaranteed that the number of cases where $$$\max(n,m) \ge 100$$$ doesn't exceed $$$5$$$. Please note that multiple stars can be in the same position, and the clouds can intersect and overlap with each other.

For each case, print a single line containing a single real number, denoting the total area (length) of shadow on the x-axis. If the answer is larger than $$$10^9$$$, print $$$-1$$$ instead.

Your answer will be accepted if and only if the absolute or relative error does not exceed $$$10^{-4}$$$.

8
1 2
0 3
-2 1 -1 1
2 1 1 1
1 2
0 3
-2 1 -1 1
1 2 2 1
2 2
10000 100
-10000 100
-10000 50 -3000 50
10000 50 3000 50
2 2
0 3
-1 10
3 2 0 1
0 1 -1 10
1 1
0 2
1 1 3 2
1 1
0 10000
-10000 9999 10000 9999
1 1
0 10000
-9999 9999 9999 9999
1 1
0 10000
-10000 1 9999 2

3.0000000000
1.5000000000
8000.0000000000
-1
-1
200000000.0000000000
199980000.0000000000
20002.0003000500

For the first sample case, the range of the shadow is $$$[-3,-1.5] \cup [1.5,3]$$$.

For the fourth sample case, the second star is covered by the second cloud, so it can't be seen anywhere.