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

某岛国的领土可以视为二维平面上的一个严格凸多边形 $C$。多边形 $C$ 有 $N$ 个顶点 $P_1,P_2,\ldots,P_N$，其中 $P_i$ 的坐标为 $(x_i,y_i)$。顶点按逆时针顺序给出。这里，$C$ 表示包含边界在内的闭多边形区域。 为了应对可能毫无预兆地到来的海啸，该国决定在领土的严格内部建造一座海啸避难所。 将海啸的波前建模为一条足够长的直线，它以单位速度移动，且形状和朝向均保持不变。令 $\theta\in[0,2\pi)$ 表示海啸来袭的方向。单位向量 $(\cos\theta,\sin\theta)$ 从避难所指向海啸来袭的海域。因此，波前垂直于该向量，并沿 $(-\cos\theta,-\sin\theta)$ 的方向移动。 在波前第一次接触领土的瞬间，全国会收到警报。假设避难所位于 $(a,b)$，令 $g(\theta)$ 为从发出警报到波前抵达避难所所经过的时间。 更精确地说，$g(\theta)$ 是使直线 $$ (x-a)\cos\theta+(y-b)\sin\theta=c $$ 与 $C$ 相交的最大实数 $c$。 下图对应样例输入中的第一组测试数据，避难所位于原点，即 $(a,b)=(0,0)$。图中展示了海啸从某个特定方向 $\theta$ 来袭时的波前与 $g(\theta)$，以及 $g(\theta)$ 随来袭方向的变化情况。第一幅图中的红色虚线表示波前第一次接触领土时的位置。  （a）某个来袭方向下的 $g(\theta)$。（b）来袭方向与 $g(\theta)$ 的关系。 定义位于 $(a,b)$ 的避难所的安全水平 $f(a,b)$ 为：当 $\theta$ 在 $[0,2\pi)$ 中均匀随机选取时，$g(\theta)$ 的期望值。 求将避难所建在 $C$ 的严格内部时，$f(a,b)$ 的最大可能值。

输入包含一组或多组测试数据。第一行包含一个整数 $T$，表示测试数据组数（$1\le T\le 10^4$）。接下来依次给出各组测试数据，每组格式如下。 ```text N x_1 y_1 x_2 y_2 ... x_N y_N ``` 整数 $N$ 是 $C$ 的顶点数（$3\le N\le 10^5$）。 对于每个 $i=1,\ldots,N$，整数 $x_i,y_i$ 是 $P_i$ 的坐标（$|x_i|,|y_i|\le 10^9$）。点 $P_1,P_2,\ldots,P_N$ 按逆时针顺序给出，构成严格凸多边形 $C$ 的顶点。换言之，$C$ 的每个内角都小于 $\pi$。 所有测试数据的 $N$ 之和不超过 $2\times 10^5$。

输出 $T$ 行，第 $i$ 行包含第 $i$ 组测试数据的最大安全水平。 如果你的输出与准确答案的绝对误差或相对误差不超过 $10^{-9}$，则会被认为正确。

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