#P17523. [ECUSTPC 2026 Fall] 永世沙漏
[ECUSTPC 2026 Fall] 永世沙漏
背景
任季节一再轮转,我却始终没能习惯。
题目描述
在欧氏平面上给定一个顶点按照逆时针顺序给出的多边形 。
记一个角度 () 为一个稳定方向,当且仅当存在 ,使得对于多边形 (含边界)内的任意一点 到直线
的垂线段完全包含在 (含边界)内,这里 是直线的一个法向方向。
请求出满足条件的稳定方向的数量,可以证明这个数量是有限的。
输入格式
第一行输入一个整数 (),表示测试数据的数量。
每组测试数据第一行输入一个整数 (),表示多边形的顶点数量。
随后 行,每行输入两个整数 (),表示多边形的第 个顶点的坐标,按逆时针顺序给出。
保证单组测试数据中所有顶点两两不同,相邻两条边仅在公共端点处相交,不相邻的两条边没有公共点。
保证所有测试数据的 。
输出格式
对于每组测试数据,输出一行一个整数,表示满足条件的稳定方向的数量。
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 组测试数据的示意图

第 2 组测试数据的示意图

第 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 组测试数据的直线和稳定方向对应
注意对应的直线不是唯一确定的。