#P17542. [JAG 2026 Summer Camp #2] Brace for Impact!
[JAG 2026 Summer Camp #2] Brace for Impact!
Problem Description
The territory of an island country can be regarded as a strictly convex polygon on the two-dimensional plane. The polygon has vertices , where the coordinates of are . The vertices are given in counterclockwise order. Here, denotes the closed polygonal region, including its boundary.
To prepare for tsunamis that may arrive without warning, the country has decided to build a tsunami shelter strictly inside its territory.
A tsunami’s wavefront is modeled as a sufficiently long straight line that moves at unit speed without changing its shape or orientation. Let denote the direction from which the tsunami arrives. The unit vector points from the shelter toward the sea from which the tsunami comes. Thus, the wavefront is perpendicular to this vector and moves in the direction .
The instant the wavefront first touches the territory, a warning is issued throughout the country. Suppose that the shelter is located at . Let be the time from when the warning is issued until the wavefront reaches the shelter.
More precisely, is the maximum real number such that the line
intersects .
The following figures correspond to the first test case in the sample input, with the shelter placed at the origin (i.e., ). They illustrate the wavefront and for a particular arrival direction , and how changes with the arrival direction. The red dashed line in the first figure is the position of the wavefront when it first touches the territory.

(a) for one arrival direction. (b) The relation between the arrival direction and .
Define the safety level of a shelter at as the expected value of when is chosen uniformly at random from .
Determine the maximum possible value of when the shelter is placed strictly inside .
Input Format
The input contains one or more test cases. The first line contains an integer , the number of test cases (). The descriptions of the test cases follow, each in the following format.
N
x_1 y_1
x_2 y_2
...
x_N y_N
The integer is the number of vertices of ().
For each , the integers and are the coordinates of (). The points are the vertices of the strictly convex polygon , given in counterclockwise order. In other words, every interior angle of is less than .
The sum of over all test cases does not exceed .
Output Format
Output lines. The -th line should contain the maximum safety level for the -th test case.
Your output will be considered correct if its absolute or relative error from the exact answer does not exceed .
2
6
-3 -2
-1 -3
2 -2
3 2
1 3
-2 2
4
6 3
7 7
4 2
5 0
3.030772067921022
2.443410850956194
Hint
In the first test case, the origin lies strictly inside . Placing the shelter at the origin gives a safety level of approximately , which is the maximum possible.