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!

题目描述

某岛国的领土可以视为二维平面上的一个严格凸多边形 CC。多边形 CC 有 NN 个顶点 P1,P2,…,PNP_1,P_2,\ldots,P_N,其中 PiP_i 的坐标为 (xi,yi)(x_i,y_i)。顶点按逆时针顺序给出。这里,CC 表示包含边界在内的闭多边形区域。

为了应对可能毫无预兆地到来的海啸,该国决定在领土的严格内部建造一座海啸避难所。

将海啸的波前建模为一条足够长的直线,它以单位速度移动,且形状和朝向均保持不变。令 θ∈[0,2π)\theta\in[0,2\pi) 表示海啸来袭的方向。单位向量 (cos⁡θ,sin⁡θ)(\cos\theta,\sin\theta) 从避难所指向海啸来袭的海域。因此,波前垂直于该向量,并沿 (−cos⁡θ,−sin⁡θ)(-\cos\theta,-\sin\theta) 的方向移动。

在波前第一次接触领土的瞬间,全国会收到警报。假设避难所位于 (a,b)(a,b),令 g(θ)g(\theta) 为从发出警报到波前抵达避难所所经过的时间。

更精确地说,g(θ)g(\theta) 是使直线

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

与 CC 相交的最大实数 cc。

下图对应样例输入中的第一组测试数据,避难所位于原点,即 (a,b)=(0,0)(a,b)=(0,0)。图中展示了海啸从某个特定方向 θ\theta 来袭时的波前与 g(θ)g(\theta),以及 g(θ)g(\theta) 随来袭方向的变化情况。第一幅图中的红色虚线表示波前第一次接触领土时的位置。

波前与安全水平

(a)某个来袭方向下的 g(θ)g(\theta)。(b)来袭方向与 g(θ)g(\theta) 的关系。

定义位于 (a,b)(a,b) 的避难所的安全水平 f(a,b)f(a,b) 为:当 θ\theta 在 [0,2π)[0,2\pi) 中均匀随机选取时,g(θ)g(\theta) 的期望值。

求将避难所建在 CC 的严格内部时,f(a,b)f(a,b) 的最大可能值。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT,表示测试数据组数(1≤T≤1041\le T\le 10^4)。接下来依次给出各组测试数据,每组格式如下。

N
x_1 y_1
x_2 y_2
...
x_N y_N

整数 NN 是 CC 的顶点数(3≤N≤1053\le N\le 10^5)。

对于每个 i=1,…,Ni=1,\ldots,N,整数 xi,yix_i,y_i 是 PiP_i 的坐标(∣xi∣,∣yi∣≤109|x_i|,|y_i|\le 10^9)。点 P1,P2,…,PNP_1,P_2,\ldots,P_N 按逆时针顺序给出,构成严格凸多边形 CC 的顶点。换言之,CC 的每个内角都小于 π\pi。

所有测试数据的 NN 之和不超过 2×1052\times 10^5。

输出格式

输出 TT 行,第 ii 行包含第 ii 组测试数据的最大安全水平。

如果你的输出与准确答案的绝对误差或相对误差不超过 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

提示

在第一组测试数据中,原点位于 CC 的严格内部。将避难所建在原点时,安全水平约为 3.030772073.03077207,这就是最大可能值。