Description

To simplify the problem, the rooftop of each building is regarded as an axis-aligned rectangle, and the rectangle is represented by the coordinates of two opposite vertices on a diagonal. During each rainfall, the rain cloud moves at a constant speed along a specified direction, and rain falls over the entire region that the cloud passes through. Model the rain cloud as a convex polygon. Given the initial position of the cloud, as well as its moving direction and speed, determine the total area of building rooftops that can receive rainfall within a certain time interval.

Input Format

The input contains multiple test cases.

The first line contains an integer $T$, the number of test cases. Then follow $T$ test cases, with one blank line between every two adjacent test cases.

For each test case, the first line contains an integer $n$, the number of buildings. The next $n$ lines each contain four integers, describing the coordinates of the two diagonal vertices of the rectangle corresponding to the rooftop of the $i$-th building.

The next line contains an integer $m$, the number of vertices of the convex polygon representing the rain cloud. Then follow $m$ vertex coordinates of the convex polygon (the order is not guaranteed, i.e., the vertices may not be given in clockwise or counterclockwise order, but the given points uniquely determine the convex polygon representing the rain cloud): ($x_1$, $y_1$), ($x_2$, $y_2$), ..., ($x_m$, $y_m$).

Next come the coordinates of the start point $s$ ($x_s$, $y_s$) and the end point $e$ ($x_e$, $y_e$), indicating that the rain cloud translates along the straight-line direction from $s$ to $e$. After that is an integer $v$, meaning the moving speed of the cloud along this direction is $v$ units of distance per minute. The last line gives the rainfall start time $hh_{start}$:$mm_{start}$ and end time $hh_{end}$:$mm_{end}$ in 24-hour format.

Output Format

Output the sum of the rooftop areas that can receive rainfall during the specified time interval, accurate to one digit after the decimal point. Your answer is considered correct if its absolute error from the reference output is within $10^{-1}$.

2

2
0 0 10 10
20 20 30 10
4
-10 8 -5 8 -5 13 -10 13
15 0 25 0
1
15:30 16:05

2
0 0 10 10
20 20 30 10
4
-10 8 -5 8 -5 13 -10 13
-5 8 19 1
1
15:30 16:30

50.0
60.5

Hint

Sample Explanation

In the first test case, there are $2$ buildings $\operatorname{B_1}$ and $\operatorname{B_2}$. The rain cloud $\operatorname{C}$ is a square (its bottom-left corner is at the point ($-10$, $8$), with side length $5$). The cloud moves uniformly in the direction from the start point ($15$, $0$) to the end point ($25$, $0$), at a speed of $1$ unit distance per minute. The rainfall starts at $15$:$30$ and ends at $16$:$05$, so the duration is $35$ minutes, and the cloud moves $35$ units along the arrow direction. As shown, the area that can receive rainfall is the shaded region, which is clearly $50.0$.

In the second test case, the moving direction of the cloud is different: it moves uniformly in the direction from ($-5$, $8$) to ($19$, $1$). The rainfall duration is $60$ minutes, so it moves $60$ units along the arrow direction. All other conditions are the same. The area that can receive rainfall is the shaded region in the figure, and its area is $60.5$. Note that in the illustration of the second test case, for convenience, the drawn “final position” of the rain cloud is not its actual final position.

Constraints and Notes

For $100\%$ of the testdata: $1 \leq T \leq 10^3$, $1 \leq n \leq 50$, $3 \leq m \leq 100$, $0 \lt v \leq 100$. All coordinate values are integers in the closed interval $[-10^5,10^5]$.

The input guarantees that the rectangles representing building rooftops do not overlap. The rainfall end time is strictly later than the start time. The start point $s$ and end point $e$ that define the moving direction are different.

Translated by ChatGPT 5