33OJ
登录 注册

#P17523. [ECUSTPC 2026 Fall] 永世沙漏

[ECUSTPC 2026 Fall] 永世沙漏

背景

任季节一再轮转,我却始终没能习惯。

题目描述

在欧氏平面上给定一个顶点按照逆时针顺序给出的多边形 P=P0P1⋯Pn−1P = P_0P_1 \cdots P_{n-1}。

记一个角度 α\alpha (0≤α<π0 \le \alpha < \pi) 为一个稳定方向,当且仅当存在 c∈Rc \in \mathbb{R},使得对于多边形 PP (含边界)内的任意一点 XX 到直线

cos⁡α x+sin⁡α y+c=0\cos \alpha\,x + \sin \alpha\,y + c = 0

的垂线段完全包含在 PP (含边界)内,这里 α\alpha 是直线的一个法向方向。

请求出满足条件的稳定方向的数量,可以证明这个数量是有限的。

输入格式

第一行输入一个整数 TT (1≤T≤1001 \le T \le 100),表示测试数据的数量。

每组测试数据第一行输入一个整数 nn (3≤n≤1053 \le n \le 10^5),表示多边形的顶点数量。

随后 nn 行,每行输入两个整数 xi,yix_i, y_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9),表示多边形的第 ii 个顶点的坐标,按逆时针顺序给出。

保证单组测试数据中所有顶点两两不同,相邻两条边仅在公共端点处相交,不相邻的两条边没有公共点。

保证所有测试数据的 ∑n≤105\sum n \le 10^5。

输出格式

对于每组测试数据,输出一行一个整数,表示满足条件的稳定方向的数量。

3
4
0 0
1 0
2 1
1 1
4
0 0
2 0
2 2
0 2
6
0 0
4 0
4 1
1 1
3 4
0 4
3
4
1

提示

样例 1 解释

:::align{center}

第 1 组测试数据的示意图

第 1 组测试数据的示意图

第 2 组测试数据的示意图

第 2 组测试数据的示意图

第 3 组测试数据的示意图

第 3 组测试数据的示意图

:::

第 1 组测试数据的直线和稳定方向对应

$$\begin{aligned} L_1:\quad &x-1=0, &\alpha_1&=0,\\ L_2:\quad &\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y-\frac{3\sqrt{2}}{4}=0, &\alpha_2&=\frac{\pi}{4},\\ L_3:\quad &-\frac{1}{\sqrt{5}}x+\frac{2}{\sqrt{5}}y=0, &\alpha_3&=\pi-\arctan 2. \end{aligned}$$

第 2 组测试数据的直线和稳定方向对应

$$\begin{aligned} L_1:\quad &x-1=0, &\alpha_1&=0,\\ L_2:\quad &y-1=0, &\alpha_2&=\frac{\pi}{2},\\ L_3:\quad &\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y-\sqrt{2}=0, &\alpha_3&=\frac{\pi}{4},\\ L_4:\quad &-\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y=0, &\alpha_4&=\frac{3\pi}{4}. \end{aligned}$$

第 3 组测试数据的直线和稳定方向对应

L:x−12=0,α1=0.L:\quad x-\frac{1}{2}=0, \qquad \alpha_1=0.

注意对应的直线不是唯一确定的。