P17542 [JAG 2026 Summer Camp #2] Brace for Impact!

The territory of an island country can be regarded as a strictly convex polygon $C$ on the two-dimensional plane. The polygon $C$ has $N$ vertices $P_1,P_2,\ldots,P_N$, where the coordinates of $P_i$ are $(x_i,y_i)$. The vertices are given in counterclockwise order. Here, $C$ 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 $\theta\in[0,2\pi)$ denote the direction from which the tsunami arrives. The unit vector $(\cos\theta,\sin\theta)$ 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 $(-\cos\theta,-\sin\theta)$. The instant the wavefront first touches the territory, a warning is issued throughout the country. Suppose that the shelter is located at $(a,b)$. Let $g(\theta)$ be the time from when the warning is issued until the wavefront reaches the shelter. More precisely, $g(\theta)$ is the maximum real number $c$ such that the line $$ (x-a)\cos\theta+(y-b)\sin\theta=c $$ intersects $C$. The following figures correspond to the first test case in the sample input, with the shelter placed at the origin (i.e., $(a,b)=(0,0)$). They illustrate the wavefront and $g(\theta)$ for a particular arrival direction $\theta$, and how $g(\theta)$ 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) $g(\theta)$ for one arrival direction. (b) The relation between the arrival direction and $g(\theta)$. Define the safety level $f(a,b)$ of a shelter at $(a,b)$ as the expected value of $g(\theta)$ when $\theta$ is chosen uniformly at random from $[0,2\pi)$. Determine the maximum possible value of $f(a,b)$ when the shelter is placed strictly inside $C$.

The input contains one or more test cases. The first line contains an integer $T$, the number of test cases ($1\le T\le 10^4$). The descriptions of the test cases follow, each in the following format. ```text N x_1 y_1 x_2 y_2 ... x_N y_N ``` The integer $N$ is the number of vertices of $C$ ($3\le N\le 10^5$). For each $i=1,\ldots,N$, the integers $x_i$ and $y_i$ are the coordinates of $P_i$ ($|x_i|,|y_i|\le 10^9$). The points $P_1,P_2,\ldots,P_N$ are the vertices of the strictly convex polygon $C$, given in counterclockwise order. In other words, every interior angle of $C$ is less than $\pi$. The sum of $N$ over all test cases does not exceed $2\times 10^5$.

Output $T$ lines. The $i$-th line should contain the maximum safety level for the $i$-th test case. Your output will be considered correct if its absolute or relative error from the exact answer does not exceed $10^{-9}$.

In the first test case, the origin lies strictly inside $C$. Placing the shelter at the origin gives a safety level of approximately $3.03077207$, which is the maximum possible.