#P17542. [JAG 2026 Summer Camp #2] Brace for Impact!
[JAG 2026 Summer Camp #2] Brace for Impact!
题目描述
某岛国的领土可以视为二维平面上的一个严格凸多边形 。多边形 有 个顶点 ,其中 的坐标为 。顶点按逆时针顺序给出。这里, 表示包含边界在内的闭多边形区域。
为了应对可能毫无预兆地到来的海啸,该国决定在领土的严格内部建造一座海啸避难所。
将海啸的波前建模为一条足够长的直线,它以单位速度移动,且形状和朝向均保持不变。令 表示海啸来袭的方向。单位向量 从避难所指向海啸来袭的海域。因此,波前垂直于该向量,并沿 的方向移动。
在波前第一次接触领土的瞬间,全国会收到警报。假设避难所位于 ,令 为从发出警报到波前抵达避难所所经过的时间。
更精确地说, 是使直线
与 相交的最大实数 。
下图对应样例输入中的第一组测试数据,避难所位于原点,即 。图中展示了海啸从某个特定方向 来袭时的波前与 ,以及 随来袭方向的变化情况。第一幅图中的红色虚线表示波前第一次接触领土时的位置。

(a)某个来袭方向下的 。(b)来袭方向与 的关系。
定义位于 的避难所的安全水平 为:当 在 中均匀随机选取时, 的期望值。
求将避难所建在 的严格内部时, 的最大可能值。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 ,表示测试数据组数()。接下来依次给出各组测试数据,每组格式如下。
N
x_1 y_1
x_2 y_2
...
x_N y_N
整数 是 的顶点数()。
对于每个 ,整数 是 的坐标()。点 按逆时针顺序给出,构成严格凸多边形 的顶点。换言之, 的每个内角都小于 。
所有测试数据的 之和不超过 。
输出格式
输出 行,第 行包含第 组测试数据的最大安全水平。
如果你的输出与准确答案的绝对误差或相对误差不超过 ,则会被认为正确。
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
提示
在第一组测试数据中,原点位于 的严格内部。将避难所建在原点时,安全水平约为 ,这就是最大可能值。