33OJ
登录 注册

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

    ID: 20268 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数学计算几何Special Judge微积分向量ICPC2026

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

Problem Description

The territory of an island country can be regarded as a strictly convex polygon CC on the two-dimensional plane. The polygon CC has NN vertices P1,P2,…,PNP_1,P_2,\ldots,P_N, where the coordinates of PiP_i are (xi,yi)(x_i,y_i). The vertices are given in counterclockwise order. Here, CC 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 θ∈[0,2π)\theta\in[0,2\pi) denote the direction from which the tsunami arrives. The unit vector (cos⁡θ,sin⁡θ)(\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⁡θ,−sin⁡θ)(-\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)(a,b). Let g(θ)g(\theta) be the time from when the warning is issued until the wavefront reaches the shelter.

More precisely, g(θ)g(\theta) is the maximum real number cc such that the line

(x−a)cos⁡θ+(y−b)sin⁡θ=c(x-a)\cos\theta+(y-b)\sin\theta=c

intersects CC.

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)(a,b)=(0,0)). They illustrate the wavefront and g(θ)g(\theta) for a particular arrival direction θ\theta, and how g(θ)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.

Wavefront and safety level

(a) g(θ)g(\theta) for one arrival direction. (b) The relation between the arrival direction and g(θ)g(\theta).

Define the safety level f(a,b)f(a,b) of a shelter at (a,b)(a,b) as the expected value of g(θ)g(\theta) when θ\theta is chosen uniformly at random from [0,2π)[0,2\pi).

Determine the maximum possible value of f(a,b)f(a,b) when the shelter is placed strictly inside CC.

Input Format

The input contains one or more test cases. The first line contains an integer TT, the number of test cases (1≤T≤1041\le T\le 10^4). 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 NN is the number of vertices of CC (3≤N≤1053\le N\le 10^5).

For each i=1,…,Ni=1,\ldots,N, the integers xix_i and yiy_i are the coordinates of PiP_i (∣xi∣,∣yi∣≤109|x_i|,|y_i|\le 10^9). The points P1,P2,…,PNP_1,P_2,\ldots,P_N are the vertices of the strictly convex polygon CC, given in counterclockwise order. In other words, every interior angle of CC is less than π\pi.

The sum of NN over all test cases does not exceed 2×1052\times 10^5.

Output Format

Output TT lines. The ii-th line should contain the maximum safety level for the ii-th test case.

Your output will be considered correct if its absolute or relative error from the exact answer does not exceed 10−910^{-9}.

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 CC. Placing the shelter at the origin gives a safety level of approximately 3.030772073.03077207, which is the maximum possible.