The 2024 ICPC Asia Hanoi Regional Contest
Hanoi University of Industry – 13 December 2024
Approaching Hurricane
Aroma lives on an island in the middle of the sea. It’s hurricane season and Aroma needs to
lead the clean up efforts after each hurricane, so she wants to know the area of the affected
region in each hurricane beforehand.
To do so, Aroma has modeled the island as a simple polygon that has n vertices and n edges.
The polygon may not be convex, but it is not self-intersecting.
There are q upcoming hurricanes. Each hurricane has the form of a moving circle with changing
radius. Here is how Aroma formally models the hurricane:
• The hurricane is modeled as a circle, with its center representing the eye of the hurricane,
and the radius of the circle representing the effective range.
• The hurricane will appear with center at point (xs , ys ) and a radius of rs .
• The hurricane’s center will gradually move from (xs , ys ) to (xt , yt ) in a straight line, and
its radius also changes gradually from rs to rt .
Formally, at some moment, if the distance between the hurricane’s current center and (xs , ys )
is ds , and the distance between that and (xt , yt ) is dt ; then the hurricane’s current radius is
ds · rt + dt · rs
ds + dt
• When the hurricane’s center reaches the point (xt , yt ), it stays there until it dissipates.
If at any moment, a point P on the island is within the circle representing the i-th hurricane,
then P is said to be affected by this hurricane.
After modeling, Aroma wants to determine the affected land area for each hurricane so she
can devise a helping plan. Please help Aroma find the area of affected land for each hurricane
passing by.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤
t ≤ 104 ). The description of the test cases follows.
• The first line contains a single integer n (3 ≤ n ≤ 3 · 105 ) – the number of points that make
up the island.
• The i-th of the next n lines contains two integers xi and yi − (|xi |, |yi | ≤ 5000) – the coordi-
nates of the i-th vertex of the polygon that represents the island.
n 6
o
• The next line contains an integer q (1 ≤ q ≤ min 3 · 105 , 10n ) – the number of upcoming
hurricanes.
• The i-th of the next q lines contains six integers xs , ys , rs , xt , yt , rt (|xs |, |ys |, |xt |, |yt | ≤
5000, 1 ≤ rs , rt ≤ 100) – representing the i-th hurricane.
It is guaranteed that:
• vertices are listed in either clockwise or counterclockwise order,
Hanoi Regional 2024 Approaching Hurricane 1
The 2024 ICPC Asia Hanoi Regional Contest
Hanoi University of Industry – 13 December 2024
• no two given vertices of the polygon have the same coordinates,
• two edges of the polygon only intersect at their shared end vertex (if any),
• the sum of n · q over all t test cases does not exceed 106 .
Output
For each of the hurricanes, print the affected area of the island. Your answer is considered
correct if its absolute or relative error does not exceed 10−6 .
Formally, let your answer be a, and the jury’s answer be b. Your answer is accepted if and only
|a−b|
if max (1,|b|)
≤ 10−6 .
Sample Input 1 Sample Output 1
3 6.000000000000
3 2.625000000000
0 0 5.333333333333
0 3 5.785398163397
4 0 5.982317997582
5 1.576314961400
0 0 4 0 0 4 0.863647609001
0 0 1 0 3 1
0 0 2 4 0 2
1 1 1 5 5 5
-1 -1 1 3 3 3
5
0 0
1 1
2 2
2 0
2 -2
1
2 0 1 6 0 2
3
3 3
2 1
1 1
1
2 2 1 2 2 1
Hanoi Regional 2024 Approaching Hurricane 2
The 2024 ICPC Asia Hanoi Regional Contest
Hanoi University of Industry – 13 December 2024
Sample Explanation
Below are the illustrations for the first test case. The triangle represents the island.
y
5
3
y
5 2
4 1
−2 −1 1 2 3 4 5
3 x
0
2 −1
1 −2
−5 −4 −3 −2 −1 1 2 3 4 5
0
x Query 2
y
−1 4
−2 3
−3 2
−4 1
−3 −2 −1 1 2 3 4 5 6 7
−5 x
0
Query 1 −1
−2
−3
Query 3
y
11
y
10 7
9 6
8 5
7 4
6 3
5 2
4 1
−3 −2 −1 1 2 3 4 5 6 7
3 x
0
2 −1
1 −2
−1 1 2 3 4 5 6 7 8 9 10 11
x −3
0
−1 Query 5
Query 4
Hanoi Regional 2024 Approaching Hurricane 3
The 2024 ICPC Asia Hanoi Regional Contest
Hanoi University of Industry – 13 December 2024
The following are the illustrations for the second test case.
y
3
1
−1 1 2 3 4 5 6 7 8 9
x
0
−1
−2
−3
The following are the illustrations for the third test case.
y
4
1
1 2 3 4
x
0
Hanoi Regional 2024 Approaching Hurricane 4
