Geometry / Numerical Methods tasks: Solution Set

Diaоsi · 2026-03-30 11:52:16 · 算法·理论

List of Geometry / Numerical Methods tasks

对这篇深度好文的拙略模仿。

难度评级如下：

17325. Gemstone Dowsing

Gemstone Dowsing

\color{cornflowerblue}{\textsf{Medium}}

你走在 x 轴上，手里拿着一个宝石探测器，它的功能如下：假设当前在位置 x^\prime，它会告诉你离你当前位置最近的一个宝石是哪一个。

你现在已经在 n 个位置 x_1,\dots,x_n 上探测到了 n 种不同的宝石，其中有 k 个宝石的具体坐标是已经确定的。对于剩下的 n-k 个宝石，你需要对每个宝石单独考虑：这个宝石最深的深度会是多少。

首先询问之间独立，因此对于特定的宝石我们可以忽略其他未知宝石对它的影响。原因是可以把其他未知宝石放在距离一些已知宝石无限近但是又有细微差别的位置上，使得仍然能够得到原本的探测序列。

因此，对于一个未知宝石 k，我们只用考虑 x 轴上前一个已知宝石 i 和后一个已知宝石 j 的限制。假设当前未知宝石的探测位置是 x_k，从 (x_k,0) 开始扩展一个圆直到撞到 (x_i,y_i) 或 (x_j,y_j) 为止，k 的位置一定在圆内。

同时，k 还不能出现在 i,j 对应的圆内，因此可能的答案位置就是圆 C_k 的底部点和 C_k 与 C_i,C_j 的交点。

只用对 x 轴做一遍扫描线，时间复杂度 \mathcal{O}(n)。

11641. Just Look Up

Just Look Up

\color{cornflowerblue}{\textsf{Medium}}

给出空间中的 n 个星星，人在原点的视野为一个顶角为 \theta\,(0\leq \theta\leq \frac{\pi}{2}) 的圆锥。可以任意调整视野的方向，若想在视野中看不到任何一个星星，\theta 最大能是多少。

将所有的点投影到以 O 为球心的球面上，若所有点都在一个半球内，输出 \frac{\pi}{2}。否则我们可以枚举三个点的外接圆作为圆锥底面，然后判断这个底面上方是否有其他点。

发现这个过程其实等价于求三维凸包，可以直接求出球面上的三维凸包，然后用每个面的外接圆更新答案即可，时间复杂度 \mathcal{O}(n\log n)。

或者也可以用朴素一点的实现：枚举两个点让圆通过这条弦，其他的点会对平面（圆其实是由平面切球得到的）的位置产生限制。找出左右限制最强的点，判断是否合法并更新答案。时间复杂度 \mathcal{O}(n^3)。

14946. Collision Damage

Collision Damage

\color{cornflowerblue}{\textsf{Medium}}

给两个凸包 P 和 Q，记所有能让 Q 通过平移与 P 相交的向量集为 D，f(\boldsymbol{t}) 表示 Q 通过 \boldsymbol{t} 平移与 P 相交的面积，求 \displaystyle\frac{1}{|D|}\iint_{D} f(\boldsymbol{t})。

答案就是 \frac{|P||Q|}{|D|}，D 是 P,Q 的闵可夫斯基差。

16202. 公园

公园

\color{cornflowerblue}{\textsf{Medium}}

给定平面上 n 个点（路灯），以及一个矩形区域 R:[0,X]\times[0,Y]。

对于矩形内任意一点 P，记其到第 k 个路灯的距离为 d_k(P)。若某个点 P 满足：对于指定的编号 i 和排名 j，d_i(P) 在所有距离中是第 j 小（即恰有 j-1 个距离严格小于它），则称 P 为一个好点。

对所有 (i,j),\,(1\le i,j\le n)，求矩形内所有满足条件的好点所构成区域的面积。

固定 i 计算所有 (i,j) 的答案。求出 P_i 与另外 n-1 个点的中垂线 L:=\{\ell_k \mid \text{bisector}(P_i,P_k)\}。L 会把平面划分成 \mathcal{O}(n^2) 个区域，每个区域对应的 j 都是唯一的，考虑计算出这个 j。

观察到每条直线会产生如下贡献：\ell_k 把平面分成两半并且让靠近 P_k 的一侧的 j 加 1。根据这条观察导出如下算法：

1. 维护一个凸包的集合 S，初始时 S 仅包含地图矩形；
2. 逐条加入直线 \ell_k，令 S 中近 P_k 侧的凸包的 j 增加 1；
3. 对于跨过直线的凸包，用 convex cut 分成两半并更新其中一半的 j；
4. 加入所有直线之后，遍历 S 中的凸包，将凸包的面积累加到 (i,j) 的答案上。

时间复杂度毛估估是 \mathcal{O}(n^4) 的，实际上把 L shuffle 之后跑的飞快。

还有一个问题就是多次求交点（i.e., convex cut 的时候用凸包上的点和直线求交）有累计误差会爆炸。解决方案是记录下凸包上的边对应的是哪条直线 \ell，\ell 能用两个整点表示出来（读入时把坐标 \times 2），然后用 \ell 求交精度就是够的。

10105. Circular Parterre

Circular Parterre

\color{gold}{\textsf{Medium-Hard}}

给定平面上 n 个喷头，每个喷头能覆盖一个圆形区域。要求构造一个尽可能大的圆，使得该圆内的每个点，都至少被某一个喷头覆盖。

输出该满足条件的最大圆。

详细版题解

圆弧不会产生限制，因此求出圆并的顶点，再对这些顶点求出 V 图，答案的圆心一定在 V 图顶点上。对每个 V 图顶点判断是否在圆并顶点多边形内即可。

朴素实现时间复杂度 \mathcal{O}(n^2)，可以做到 \mathcal{O}(n\log n)。

10161. Symmetric Boundary

Symmetric Boundary

\color{orangered}{\textsf{Hard}}

给出平面上的 n 个点，求出面积最小的中心对称凸包，使得 n 个点都在凸包的边界上。保证任意三点不共线。

记原本的点集为 P，关于对称中心 X 的对称点为 Q。

枚举点对 P_a,P_b，直线 L(a,b) 表示过 (P_a+P_b)/2 和 (P_{a+1}+P_b)/2 的直线，建出所有直线的 Arrangement \mathcal{A}(L)（i.e., 所有直线将平面分割成的所有区域）。L(a,b) 的意义是最终答案的中心跨过这条直线后，P_b 会被 P_aP_{a+1} 的对称边吞掉。

总共有 \mathcal{O}(n^2) 条直线，形成 \mathcal{O}(n^4) 个 Cell，每个 Cell 是个凸多边形。对于每个 Cell 内的 X，\textsf{conv}(P\cup Q) 关于 X 是个线性函数，因此极值会在 Cell 的边界上取到。于是只需要取 \mathcal{A}(L) 中的每个交点作为 X 判断合法并且暴力计算答案。

时间复杂度 \mathcal{O}(n^5\log n)。

10327. Convex Hull of Intersections

Convex Hull of Intersections

\color{cornflowerblue}{\textsf{Medium}}

给出大小为 n 的直线集合 L，求出其 Arrangement \mathcal{A}(L) 交点的凸包。

对于斜率相同的直线，只保留最外侧的两条，然后把它们当作斜率相反。然后把所有直线按照斜率排序，求出相邻两条直线的交点集合 P，最后求 \textsf{conv}(P) 即可。

时间复杂度 \mathcal{O}(n\log n)。

9978. Keystone Correction

Keystone Correction

\color{gold}{\textsf{Medium-Hard}}

一个投影仪被描述为一个源点的点光源和一个像矩形，投影到墙平面上。

投影可能不正，也可能不完全落在矩形荧幕上，因此可以选择像矩形里的四个角来确定一个四边形来校正画面，使得投影为一个与像矩形同宽高比且平行于地面的矩形，且完全落在荧幕上。

问校正后的画面最大面积是多少。

将像矩形投影到平面上后，会形成一个凸多边形 P，同时荧幕也对应一个凸多边形 Q。题意转化为在 P\cap Q 内找到一个最大的 w:h 的矩形。

将三维问题转化为二维问题后，我们可以二分答案矩形的大小，然后检查该矩形能不能被塞进两个凸多边形的交集内。

先思考一个弱化版的问题：如何判断一个凸多边形 A 能不能通过平移完整地放进另一个凸多边形 B 中。考虑对每个端点 (x_i,y_i) 求出有哪些向量集使得该端点能够与 B 有交，答案就是 D_i=B-(x_i,y_i)，即二者的闵可夫斯基差。若所有的端点都能在 B 内部，根据凸性的定义它们两点的连线也一定在 B 内部，因此转化成判断若干个凸包是否有交。

事实上，每种平移 D_i 只有均摊 \mathcal{O}(1) 条边限制最强，可以通过旋转卡壳的方式求出 B 的每条边会在 A 的哪个端点进行平移时成为最强的限制，然后求半平面交即可。时间复杂度 \mathcal{O}(|A|+|B|)。

回到原题，每次二分时求出待检查的矩形对 P 造成的半平面限制和对 Q 造成的限制放在一起跑同一个半平面交，就能判断是否能在 P\cap Q 中放置。

通过 convex cut 求半平面交优化精度，反正单次复杂度都是 \mathcal{O}(1) 的。总时间复杂度 \mathcal{O}(T\log\epsilon^{-1})。

9919. Concave Hull

Concave Hull

\color{cornflowerblue}{\textsf{Medium}}

给定一个大小为 n 的点集，求这个点集的凹包的总面积。凹包定义为有且仅有一个内角大于 \pi 且能包含点集中所有点的简单多边形。

枚举内角大于 \pi 的顶点，以该点为原点做极角排序。枚举断开凸包上的边，与原点构成的三角形中间包含若干个点，在极角序上是一个连续的区间。区间上相邻的两个点都可以确定凹包的形态。

相邻的两个点将区间划分成一段前缀和后缀，它们与三角形上的两边分别构成两个凸包。于是凹包的面积可以表示成：凹包 - 三角形 + 两个凸包。

预处理出该区间前后缀点集的凸包面积，在 Graham Scan（i.e., 极角排序求凸包）过程中，每加入一个点就用增量法递推出当前栈内的凸包面积。枚举相邻两个点时就能 O(1) 回答凹包的面积。

时间复杂度 \mathcal{O}(n^2\log n)。

9808. Fragile Pinball

Fragile Pinball

\color{gold}{\textsf{Medium-Hard}}

给定一个有 n 条边的凸多边形，有一个沿直线运动的弹球，如果遇到边界时可以选择做反射，如果同时在两条边上可以选择做反射边界及其顺序，但是每条边只能反射一次弹球。对每个 k=0,1,\cdots,n 计算弹球被反弹至多 k 次时，弹球在凸多边形内可以行进的最长路程。

枚举反射的边的顺序，按照顺序将多边形做一系列对称，相当于将弹球的路径展开成一条直线。即需要求一条最长直线经过所有反射边和起始/目标多边形。

此时得到的多边形可能是自相交的，但是自交的部分一定不会对答案产生影响（直线扫不到），因此还是可以使用类似于机场建设的分析方法得到结论：弹球路径至少经过以下两个不同的点，起始多边形的顶点、目标多边形的顶点、沿途反射边的端点。

枚举直线并求出与两个多边形的交点，再判断这条直线是否经过所有反射边，时间复杂度 \mathcal{O}(n!\cdot n^3)。

9037. Ancient Maps, Hidden Danger

Ancient Maps, Hidden Danger

\color{orangered}{\textsf{Hard}}

给出 m\,(m\leq 30) 个不交简单多边形（总点数 n\leq 90），从无限远的所有方向打光，求出多边形遮挡的阴影面积。

记录一下怎么完成这个毒瘤题的。阴影面积不好算，考虑算被照亮的面积，如果点 P 能被照亮，那么可以稍微把光线旋转一些，使得照亮 P 的光线恰好经过一个多边形的顶点 A。于是可以把 P 当成是 A 照亮的。

思考点 P 被点 A 照亮的充分条件，需要满足

• 线段 \overline{AP} 不与任何边相交，不经过任何多边形内部
• 射线 \overrightarrow{AP^\prime} 不与任何边相交/经过多边形内部，P^\prime 是 P 关于 A 的对称点

枚举每个顶点 A 计算它能够照亮的区域。根据上面的两个条件，把所有的顶点及其关于 A 的对称点以 A 为原点做极角排序，每个极角区间一定是极小的——要么全被照亮要么全部无法被照亮。

接下来计算一个极角区间能够被照亮多少，假设这个区间的两个向量是 \overrightarrow{AB} 和 \overrightarrow{AC}。先判断射线 \overrightarrow{AB^\prime} 和 \overrightarrow{AC^\prime} 是否在多边形外，可以在射线方向上选择一个略微超出值域范围的点，然后用判断线段在多边形外的方法进行判断。

如果反向射线没有相交，那么找到与 \overrightarrow{AB},\overrightarrow{AC} 相交的一条边，设交点分别为 E,F，判断 \overline{AE} 和 \overline{AF} 是否在多边形外。两条射线会相交在同一条边上，如果没有交可以跳过这个区间，说明这个区域会被其他点照亮。若能够找到（唯一）一对符合条件的 E,F，那么 \triangle AEF 就是一个会被 A 照亮的区域。

以多边形的每个顶点为原点，能够找出 \mathcal{O}(n^2) 个被照亮的三角形。将这些三角形取并集就是所有被照亮的区域，然后用全集 - 多边形面积 - 照亮区域就是答案。这里的全集是所有点形成的凸包的面积，因为在上面的算法中每条光线都是由两个整点确定的，那么外侧的边就是凸包的边。

然后就是一些 corner case，大概有这些：

• 怎么判断线段在多边形外？把逆时针多边形改成顺时针，然后判断线段是否在多边形内部就行；需要处理好线段恰好跨过顶点/和边界共线的情况
• 极角扫描线的时候注意区间退化的情况
• 如果有多边形是三角形，上面的算法可能会把这个三角形当作照亮面积；一个不用动脑的解决方案是把多边形也丢在一起求并
• 三角形的顶点是两条直线的交点，求三角形并还要再次求交点，两重交点可能会爆精度；注意到三角形的边的直线是两个整点产生的，拿这两个整点用于后续求交可以优化精度

时间复杂度瓶颈在于求面积并，由于有 \mathcal{O}(n^2) 个三角形，因此时间复杂度为 \mathcal{O}(n^4\log n)。官解给出的面积并的做法是：对所有线段交点建平面图然后单独计算每个 Cell 的面积，不需要每次都排序因此十分高效；实际上常规扫描线做法的效率也比较可观，可以在 ~3000ms 的时间通过。

9049. Machine Learning with Penguins

Machine Learning with Penguins

\color{gold}{\textsf{Medium-Hard}}

给出三维空间中的 n 个点，判断能不能找到一个底面在 z 平面的的圆柱体，使得 n 个点都在圆柱体表面。

可以把圆柱的顶面调整到 \max z_i，这样点集就会被分为两个集合：在底面/顶面的点集 P，在侧面的点集 Q。Q 中的点得恰好在一个圆上，P 中的点要在 Q 确定出来的圆内/圆上，转化为二维问题。

分类讨论：

如图，C,D,E 造成的约束分别为 [\cot C,\infty),\,(-\infty,\cot D],\,[\cot E,\infty)。判断所有区间交是否为空即可。

卡精度，需要全整数实现，精度要求最高的地方在于判断点 p 与三角形 \triangle abc（逆时针）的外接圆的关系：

9728. Catch the Star

Catch the Star

\color{gold}{\textsf{Medium-Hard}}

给定 n 个凸形障碍 M_i 和一个目标多边形 S，求出线段 \overline{(l,0)\,(r,0)} 上能够完整看到 S 的位置的长度。

对于每个障碍 M_i 求出它与 S 的两条内切线 m_1s_1, m_2s_2，不失一般性令 m_1\rightsquigarrow m_2 表示 M_i 上逆时针的一段弧，并且这段弧被夹在两条内切线中间。

那么 \overrightarrow{m_1s_1}, \overrightarrow{m_1m_2},\overrightarrow{s_2m_2} 的左开半平面交就是无法完整看到 S 的区域。把三个半平面分别与 \overline{(l,0)\,(r,0)} 求交，再把三个区间求交得到一个开区间 I_i。\bigcup_{i\in [n]} I_i 就是无法完全看到 S 的位置，取个补就能得到答案。

注意由于遮挡的位置是开区间，因此可能能够完整看到 S 的长度为 0 但是不为空（i.e., 有一些特定位置能够完整看到 S）。故求区间的部分需要有理数实现精确计算。

10479. The Farthest Point

The Farthest Point

\color{cornflowerblue}{\textsf{Medium}}

分类讨论。

9576. Ordainer of Inexorable Judgment

Ordainer of Inexorable Judgment

\color{cornflowerblue}{\textsf{Medium}}

那维莱特。

9554. The Wheel of Fortune

The Wheel of Fortune

\color{gold}{\textsf{Medium-Hard}}

一个匀质凸多边形转盘由旋转中心划分得奖区域。当转盘的重心不在旋转中心时，转盘永远会停留在重心在最低点处，被向下的指针指向。

一个点配重 w 将会被均匀随机放在转盘上。问每个区域成为获奖区域的概率。转盘单位密度为 1，转盘面积 S 满足 \max\big\{\frac{S}{w},\frac{w}{S}\big\}\leq 10^3。

设凸多边形的重心为 c，配重的坐标是 p，那么转盘新的重心是：

其中只有 p 是一个在凸多边形内的变量，其余为常量。因此，c^\prime 是关于 p 的线性函数。等价于在一个被缩放的凸多边形范围内随机一个点作为 c^\prime，在被缩放的凸多边形里，落在原来每个区域的面积占比即是答案。

注意到出题人为了避免精度问题把值域开的很小，而根据经典结论，值域为 \mathcal{O}(V) 的严格凸包大小是 \mathcal{O}\big(V^{2/3}\big) 的。换句话说，凸包上有用的边不会太多。对于原本的每个划分区域，我们把划分这个区域的两条射线和凸包的边丢到一起做半平面交，复杂度只有 \mathcal{O}\big(nV^{2/3}\big)。

事实上只需要用 convex cut 切凸包两次，不仅跑得快精度还高，这样就完美地避免了各种分类讨论。这个做法实际表现是非常优秀的，在使用 double 的情况下只跑了 69ms/7000ms。

9316. Boxes

Boxes

\color{gold}{\textsf{Medium-Hard}}

给定三维空间中 n 个点，将其划分为若干不相交集合 S_1,\dots,S_k。要求任意两集合的凸包满足：要么体积不相交，要么其中一个包含于另一个。

目标是最大化 \sum |\mathsf{conv}(S_i)|。

若干个凸包互相嵌套最优，因此可以不断求出最外层凸包并删去。使用卷包裹法，单次时间复杂度为 \mathcal{O}(nd)，总时间复杂度为 \mathcal{O}(n^2)。

还有一种能过的写法是，将点集随机打乱，然后每次跑朴素的增量法。出题人说尝试过卡掉它或者证明它，都没成功，怀疑有些深刻的道理说明是对的，但应该不简单。

8779. Square of Triangles

Square of Triangles

\color{orangered}{\textsf{Hard}}

给四个三角形，允许平移旋转对称。问在不重叠并且没有间隔的情况下能不能拼成一个正方形。

超级无敌巨大邪恶混乱分类讨论

7693. Convex Hull Extension

Convex Hull Extension

\color{gold}{\textsf{Medium-Hard}}

给定大小为 n 的凸包，求出平面上有多少个点能够与原本的点构成大小为 n+1 的严格凸包。

考察相邻三条边 \overline{AB},\overline{BC},\overline{CD} 的结构。数出 \overrightarrow{AB} 和 \overrightarrow{DC} 的两条射线夹着的区域的整点数：先将两条边尽可能延长整数倍，使得两条边不相交，构成一个整点四边形 BB^\prime C^\prime C。通过皮克定理输出四边形内的点，剩下的三角形内整点数不超过 2|V|，可以直接暴力计算。

时间复杂度 \mathcal{O}(nV)。

7862. Land Trade

Land Trade

\color{cornflowerblue}{\textsf{Medium}}

给出逻辑表达式，有 n 个原子命题形如 [a,b,c]。当 ax+by+c\geq 0 时值为真否则为假。逻辑运算符包含与、或、非、异或。

你需要在矩形区域 R:=\{(x,y)\mid x_{\min}\leq x\leq x_{\max},y_{\min}\leq y\leq y_{\max}\} 中，求出能使逻辑表达式为真的区域的总面积。

通过 convex cut 求出直线集合 L 的 Arrangement \mathcal{A}(L)。然后对每个 Cell 判断命题是否为真然后累加面积即可。

时间复杂度 \mathcal{O}(n^3)。

7783. Military Maneuver

Military Maneuver

\color{gold}{\textsf{Medium-Hard}}

给出 n 个点和一个矩形区域 R:[0,X]\times[0,Y]，在 R 内均匀取点，求出以该点为圆心的最小覆盖圆环的期望面积。

求出 V 图与最远点 V 图，每个 Cell 对期望的贡献可以单独算。

7734. Intersection over Union

Intersection over Union

\color{gold}{\textsf{Medium-Hard}}

给定一个矩形 A，求出一个轴平行矩形 B ，使得 J(A,B)=\frac{|A\cap B|}{|A\cup B|} 最大。

两个矩形的中心重合最优，并且此时 J(A,B) 关于 B 的宽 w 和高 h 是个凸函数，用三分套三分求出极值。需要注意算交面积时的精度。

10561. Spaceship Exploration

Spaceship Exploration

\color{cornflowerblue}{\textsf{Medium}}

平面上有一个大小为 n 的凸形障碍 Q，给定起点和终点 S,T，在只允许一次拐弯并且把不撞到 Q 的情况下，S 到达 T 的最短路线是什么。

求出 S,T 与 Q 的切线，然后取交点作为拐弯点即可。特判不需要拐弯的情况。时间复杂度 \mathcal{O}(n\log n)。

7568. Keychain

Keychain

\color{orangered}{\textsf{Hard}}

给出二维平面上大小为 n 的点集 S，求出一个最小的半径 r，使得能够找到一个生成圆 \Gamma 经过所有以 p\in S 为圆心半径为 r 的圆。

输出 \Gamma 圆心的精确坐标（有理数）和半径 R；允许 \Gamma 退化成一条直线（R\to+\infty 的圆），此时输出直线的精确表达式 ax+by=c。

这是一个最优化问题，若指定圆心 p，那么对应的最优 r 就是 \frac{1}{2}(\max d(p_i,p)-\min d(p_j,p))，同时可得 R=\frac{1}{2}(\max d(p_i,p)+\min d(p_j,p))。现在就是要找到一个点 p 使得目标函数 \frac{1}{2}(\max d(p_i,p)-\min d(p_j,p)) 最大。

对点集 S 求出 V 图和最远点 V 图，答案一定在两个 V 图的 Cell 之间的交点取到。因此可以枚举 \mathcal{O}(n^2) 对 Cell 求交点然后更新答案。V 图和最远点 V 图都可以归约三维凸包：

下凸壳对应 V 图的对偶，上凸壳对应最远点 V 图的对偶，这样就可以快速求出每个 Cell 边界对应的半平面。把两个 Cell 的半平面求交就能找出交点。有一个小技巧是读入时将坐标 \times 2，这样每个半平面都可以用整数表示，以便求出精确的交点。

这题还需要处理好退化的情况：

2. 所有点共线；
3. 所有点共圆，在三维上表现即所有点共面；

虽然 V 图有很好的性质，但是两个 V 图的交点个数仍然会达到 \Omega(n^2) 个，所以时间复杂度仍然是 \mathcal{O}(n^2) 的。

5142. Grid Points

Grid Points

\color{maroon}{\textsf{Very Hard}}

给定第一象限内的一个简单多边形，考虑其中所有整点 (x,y)（含边界）。按斜率 y/x 从小到大排序；若相同，则按 (x,y) 字典序排序。输出第 k 个点。

详细版题解

8039. Infinite Strife

Infinite Strife

\color{orangered}{\textsf{Hard}}

给出平面上 n 个点 p_1,\dots ,p_n，再给出经过每个点的 m 个闭半平面以及它们的对称闭半平面（共 2m 个）。对每个点选择一个半平面 H_i，求出有多少种选法使得所选半平面的并集能够覆盖目标矩形 S=[-R,R]^2。

直接做比较难，正难则反，考虑其反问题

这里的 T 是开矩形 (-R,R)^2，因为 \overline{H_i} 是开半平面。因此我们只需要求出有多少种选法可以使得半平面与矩形 T 的交非空，然后用总方案数 (2m)^n 减去即可。

观察到对于每个点 p_i，第 k 个半平面和第 k+m 个半平面共用同一条直线但是方向相反，因此我们可以把选半平面的过程分为：

1. 先选择 n 条无向直线，记其集合为 L；
2. 给 L 中的每条直线定向。

定向的方案数总共有 2^n 种，但是考察 L 在 T 内的 Arrangement \mathcal{A}(L) 中的 Cell，发现每个 Cell 恰好对应唯一一种定向方案，使得这些半平面与 T 有非空交。因此我们可以把反事件的方案数转化成记录 Cell 的个数 F 的期望 \mathbb{E}[F]，再乘以选择直线的方案数 m^n：

用平面图欧拉公式把 F 展开

此处 L 表示与 T 有交的本质不同直线数；r_q 表示对于一个关键点 q\in T，有 r_q 条本质不同的直线经过它，这里的关键点可能是两条直线的交点，也可能是输入的点 p_i。现在只需要计算 \mathbb{E}[L] 和 \mathbb{E}\left[\sum_{q\in T}(r_q - 1)\right]。

Case 1: \mathbb{E}[L]

对于一条固定的直线，假设有 c 个点能够生成这条直线，那么它至少被选种一次的概率为 \Pr(L)=1-\left(\frac{m-1}{m}\right)^c。对 m^n\cdot \mathbb{E}[F] 的贡献即为：

Case 2: \mathbb{E}\!\left[\sum_{q\in T}(r_q - 1)\right]

考察 T 内的一个关键点 q，它的贡献是 r_q-\mathbf{1}_{[r_q>0]}，因此我们可以继续把这个期望拆成 \mathbb{E}[r_q] 和 \Pr(r_q>0) 分别计算。

SubCase 3: \mathbb{E}[r_q]

对每个关键点 q，过它的直线由 q 自身和每个点生成的直线的离散方向 k\in[0,m-1]（即角度为 \frac{k\pi}{m}）唯一确定。因此我们可以记录 \#k 表示有多少个点 p_i 生成的第 k 条直线经过 q，那么对于 k 这类直线而言，至少有一条经过 q 的概率为：

因此

SubCase 4: \Pr(r_q>0)

对 q 的类型进行分类讨论，q 可能是一个给定点 p_i 或者是一个交点，记

若 \#c_0>0，显然 \Pr(r_q>0)=1；否则就要求 \#c_1 个点生成的直线都避开 q，此时对答案的贡献为：

因此我们需要分别计算每种直线和所有关键点 q 的贡献。精细一点实现可以做到 \mathcal{O}(n^2m^2)，我写了个 \mathcal{O}(n^3m^2) 的东西也过了。

6813. Union of Circular Sectors

Union of Circular Sectors

\color{orangered}{\textsf{Hard}}

给出 n 个劣弧扇形，保证没有两个扇形的半径边平行，求出扇形的面积并。

#7310 的弱化版，正赛直接搬原题有点没素质了。

5104. Guardians of the Gallery

Guardians of the Gallery

\color{orangered}{\textsf{Hard}}

一个艺术画廊可以看成一个简单多边形，画廊中有一个保安和一个雕塑，保安和雕塑的位置都严格位于多边形内部的不同点。

雕塑可以认为是一个无限小的圆形，保安需要从当前位置出发，在多边形内部走到一个能够看到雕塑至少一半的位置。你需要求出这个最短距离。

详细版题解

保安只会走多边形顶点之间的线段（起点终点也当作顶点）。枚举两端点判断线段是否在多边形内，加入边集 E。

能够看到雕塑的位置是多边形内的一个区域。而这个区域的边界形如雕塑位置和多边形上端点的连线。枚举这些射线，找到在多边形内的极长线段（即最长的合法可视边界）。求出每个顶点到这条线段的最短路线，判断这条路线是否在多边形内并加入 E。

最后对 E 跑最短路即可，时间复杂度 \mathcal{O}(n^4)，corner case 分析以及如判断可视边界见详细版题解。

1818. Apple Orchard

Apple Orchard

\color{gold}{\textsf{Medium-Hard}}

给定 n 棵苹果树，每棵树会在平面上形成一个圆形阴影区域。

有 q 次询问，每次给出一个与坐标轴平行的矩形，要求计算该矩形内被阴影覆盖的面积占矩形总面积的百分比。

询问相当于是求一个矩形和圆并的交。求出 Power Diagram，回答每个询问时遍历每个 Cell；将 Cell 的多边形和矩形求交，再和 Cell 管辖的圆求交，对所有 Cell 求和得到答案。

时间复杂度 \mathcal{O}(n(n+q))。

5067. Two Walls

Two Walls

\color{cornflowerblue}{\textsf{Medium}}

在二维平面上，给定起点 S 终点 T 和线段 AB,CD。从 S 出发，只能走直线，问不经过 AB,CD 上任何的点，最少要变换几次方向才能到达 T。

注意到答案至多为 2。0 和 1 比较简单故略去，考察答案为 2 的情况。

当线段 ST 与 AB,CD 都交于非端点时，设 ST 左侧的两点为 A^\prime 和 B^\prime，判断射线组 SA^\prime, TB^\prime 和 SB^\prime, TA^\prime 是否都相交。

若是，则答案为 1，否则为 2，另一侧的判断同理。整个过程需要判断线段相交，是否在端点相交，以及判断两点是否在线段的同一侧。判断都可以用叉乘表示，可以全整数运算。

9861. Mountain Is Quiet and Alone

Mountain Is Quiet and Alone

\color{cornflowerblue}{\textsf{Medium}}

有一个形如 n 个点凸包的山峰，山顶上竖着一个长度为 1 的棍子，求棍子滚落过程中其中一个端点扫过的长度。

模拟棍子滚落的过程即可，需要细致讨论（i.e., 一个角卡在棍子中间，哪边是棍头）。棍子滚落的位置可以通过二分求出。时间复杂度 \mathcal{O}(n\log\epsilon^{-1})。

10774. Monitored Area

Monitored Area

\color{orangered}{\textsf{Hard}}

在大小为 n 的简单多边形内放置 m 个守卫，求所有守卫能够看到的面积的总和。

跟 #9037 差不多，以每个守卫为原点做极角排序，求出每个极角区间内能够照亮的三角形，最后对 \mathcal{O}(nm) 个三角形求面积并即可。时间复杂度 \mathcal{O}(n^2m^2\log(nm))。

6612. A Bite of Teyvat

A Bite of Teyvat

\color{gold}{\textsf{Medium-Hard}}

在线求出一排圆（圆心位于 y=0 上）的并的面积。

转化成 Power Diagram，等价于求 (x_i,x_i^2-r_i^2) 的动态凸包，每次计算面积的增量即可。时间复杂度 \mathcal{O}(n\log n)。

6436. Paimon Polygon

Paimon Polygon

\color{gold}{\textsf{Medium-Hard}}

对于大小为 n 的点集 S 和原点 O=(0,0)，求出一个划分 A,B\,(A\cup B=S,A\cap B=\varnothing)，使得 A\cup O,\,B\cup O 是凸集，且他们的轮廓只在 O 相交。

你需要令 A\cup O,\,B\cup O 的凸包周长总和最大。

详细版题解

两凸包相互包含的情况是平凡的，只需要求两次凸包就能判断。接下来分成两种情况讨论，讨论 O 是否在 S\cup O 凸包的边界上。

第一种情况：O 在 S\cup O 凸包的边界上

将极角序上相邻的两个点分开，然后分别判断前半部分和后半部分的点集是否是凸集。

第二种情况：O 不在 S\cup O 凸包的边界上

给出大小为 n 的点集 P，有 m 次询问，每次询问一个点集 Q_i，输出 2\cdot|\textsf{conv}(P\cup Q)|（凸包面积的两倍）。

对于每个 u\in Q_i，先判断是否在 \textsf{conv}(P) 内，若在凸包内则跳过这个点；若不在，求出 u 在 \textsf{conv}(P) 上的两个切点 p,q。

求出所有形如 u,p,q 的点构成的点集的凸包 U。对于 U 上相邻的两个点，若都在原凸包上，答案累加原凸包上这段弧的叉积和；否则直接累加这条边的叉积。

叉积和的查询可以通过前缀和实现，注意凸包上需要断环成链。时间复杂度 \mathcal{O}((n+m)\log n)。

5060. Circle

Circle

\color{orangered}{\textsf{Hard}}

给定平面上 n 个半径为 r 的圆，求所有圆的交的面积，保证圆心集合是个凸包。

注意到交集一定是个凸集，所以凸包这个限制没啥用——能产生边界的只能是凸包上的点。由于半径全部相同，因此任意两个圆的交弧只能是劣弧。于是我们就可以得到一个魔改的半平面交算法：

• 维护双端队列保存交集边界的弧；
• 按照凸包顺序考虑圆，取出当前圆和队尾圆的交弧；
• 不断淘汰队尾的弧，直到两弧相交，更新队尾弧的端点；
• 淘汰队头同理，最后将当前的弧入队。

最后的面积就是多边形加上若干个弓形的面积。时间复杂度 \mathcal{O}(n)，本题中虽然 n 开的很小，但是出题人还是通过多测卡掉了 \mathcal{O}(n^2) 的 convex cut 算法。事实上这个值域下造不出更大的凸包，而值域开太大会产生精度问题。

8019. Wowoear

Wowoear

\color{gold}{\textsf{Medium-Hard}}

给定一条折线段路径，用另一条线段连接折线段的两点，使得新线段与折线段无交，并且节省的路径长度尽可能长。

根据机场建设的分析，新线段至少经过一个点，或者是以两折线端点为起终点的线段。

后者的求解是平凡的，对于前者可以枚举中心点 A，然后把其他点以及它们和 A 的对称点做极角排序。在每个极角区间内，朝着两个方向打射线碰到的线段一定是极小的。

每个极角区间内，答案关于角度单峰，可以三分求解。时间复杂度 \mathcal{O}(n^2\log\epsilon^{-1})。

2069. Geometry PTSD

Geometry PTSD

\color{orangered}{\textsf{Hard}}

构造单位球面上的三个点 A,B,C，满足：\min(|AB|,|AC|,|BC|)\ge 1.7；原点到平面 ABC 的距离在 (0,\,1.5\times 10^{-19}] 内。

取 (10^6,0,0),(0,10^6,10^6),(-10^6,0,-10^6) 三个点，然后在三个点周围调整。checker 需要仔细实现。

1196. Fun Region

Fun Region

\color{orangered}{\textsf{Hard}}

给定一个简单多边形。若点 P 能通过不自交、始终顺时针转弯且不穿越多边形的折线（螺旋路径）到达所有顶点，则称 P 为合法点。求所有合法点构成区域的面积。

结论是，对于每个多边形的凹角 ABC，用射线 \overrightarrow{AB} 切简单多边形，最后得到的面积就是答案。

时间复杂度 \mathcal{O}(n^2)。

5046. Moon

Moon

\color{maroon}{\textsf{Very Hard}}

单位球面上有固定点 a_1,\dots,a_n，以及一个均匀随机点 a_0。若存在一个半球包含所有点 a_0,\dots,a_n，则 f=1，否则 f=0。求 \mathbb{E}[f]。

特判共线/共面的情况，接着对变换前的点求三维凸包，若 O 严格在凸包内，则答案为 0。

否则，求答案等价于求球面凸包的面积。遍历三维凸包的每个面，若该面不包含 O，则将这个球面三角形的面积计入答案，因为它关于 O 对称的面中如果出现了 a_0 一定有 f=0。

球面三角形的计算方式为 \alpha + \beta + \gamma - \pi，其中 \alpha,\beta,\gamma 为球面两条边与 O 构成的两个平面的二面角，可以用法向量叉乘 + 反三角函数算出。

本题究极卡精度（见 #2069），求凸包的部分需要实现全整；求二面角的部分的最大中间量达到了 10^{48}，__int128 无法存下，但是可以在容忍一点精度损失的情况下转成 long double。

注意算反三角的时候需要转化成 \tan^{-1} 而不是 \cos^{-1}，因为 \cos \in [-1,1]，压缩值域会造成大量精度损失。

时间复杂度 \mathcal{O}(n\log n)。

2444. Closest Pair of Segments

Closest Pair of Segments

\color{gold}{\textsf{Medium-Hard}}

给定 n 条线段，求出它们之间的最近距离。

二分答案 d，转化成判断 n 个香肠形是否有交。可以魔改判断线段交的扫描线算法求解：以香肠形的左极点和右极点作为扫描线的时刻，每次判断相邻香肠形是否有交时检查原线段对的距离是否 \leq d 即可。

时间复杂度 \mathcal{O}(n\log n\log \epsilon ^{-1})。

2309. 保镖

保镖

\color{maroon}{\textsf{Very Hard}}

给大小为 n 的点集 P 和一个矩形区域 R。在矩形区域内均匀随机选择点 O，将 P 中所有点以 O 为中心进行半径为 1 的反演变换。

记变换后点集为 P^\prime，其严格凸包顶点数为 C，求出 \mathbb{E}[C]。

根据平面图的性质，将数凸包大小 C 转化成数三角剖分的个数T，它们的关系为：C=2n-2-T。指定三角剖分为 Delaunay Triangulation，接下来只讨论 T 的变化。

Delaunay Triangulation 中的每个三角形都满足空圆性：三角形外接圆内没有其他点。称这种圆为内圆，反之若外接圆内包含所有点则为外圆。

对于任意一个内圆，若反演中心在该圆内，反演后该内圆会变成外圆，其他不包含该点的内圆还是内圆。反之，若在某个外圆内，反演后该点变成内圆，其他不包含该点的外圆还是外圆。

数三角剖分个数就是数内圆的个数，根据期望的线性性，每个内外圆对答案的贡献可以单独计算：都是形如一个圆与矩形 R 的交，算出交区域的面积即可。

如何求内圆与外圆？将点 (x,y) 投影到抛物面 z=x^2+y^2 上，即变换为 (x,y,x^2+y^2)。任意平面切该抛物面在 xOy 平面上的投影都是一个圆。因此点集的下凸壳中的每个面都对应一个内圆（所有点都在平面上可以推出没有点在投影的圆内），同理上凸壳的每个面对应一个外圆。

因此只需要求一个三维凸包，需要特殊处理一些点共竖直面的情况，由于 z=x^2+y^2 这个平面本身就是凸的，因此共竖面的点的轮廓自然是个凸包。如果你的三维凸包板子比较鲁棒的话，是能够输出这个凸面的一个三角剖分的。该三角剖分的每个三角对应一个外圆，但是该外圆会退化成一个半平面，因此求出半平面与矩形的交即可。

时间复杂度 \mathcal{O}(n\log n)。

2433. Panda Preserve

Panda Preserve

\color{gold}{\textsf{Medium-Hard}}

给定一个多边形，其每个顶点放置一个接收器，覆盖半径相同的圆形区域。求最小半径，使这些圆的并集能够覆盖整个多边形区域。

求出 V 图，最后被覆盖到的点一定在 V 图上，判断每个顶点是否在多边形内，然后更新答案即可。时间复杂度 \mathcal{O}(n^2)。

6445. Stars in a Can

Stars in a Can

\color{gold}{\textsf{Medium-Hard}}

给出空间中的 n 个星星，求出一个最小的圆柱体能包住这 n 个星星，并且其中一个底面上至少有三个星星。

求出三维凸包，枚举每一个面作为底面然后将所有点投影到这个底面上跑最小圆覆盖即可。时间复杂度 \mathcal{O}(n^2)。

2767. Airport Construction

Airport Construction

\color{gold}{\textsf{Medium-Hard}}

给定一个大小为 n 的简单多边形，求出一条在多边形内最长的线段。

可以通过平移和旋转的微扰证明：最长线段至少经过多边形的两个端点。端点 A,B，判断线段 AB 是否在多边形内，然后再求 AB 两端能延伸出去的最长距离。

暴力的做法是把直线 AB 与多边形的所有交点都求出来，排序后检查相邻两个交点的中点（取线段上任意一点均可）在不在多边形内。若在，则这一小段线段就都在多边形内，更新答案。这个做法的复杂度是 \mathcal{O}(n^4)，常数较小可以通过。

精细实现可以做到 \mathcal{O}(n^3)：先判断多边形上是否有边跨过 AB，若没有则检查 AB 中点是否在多边形内。然后分别枚举第一条跨过射线 AB 两侧射线的边，求出交点更新答案。

11817. Resonators

Resonators

\color{gold}{\textsf{Medium-Hard}}

给出平面上 n 个圆 C_i，记这些圆的并集区域为 \Omega:= \bigcup_{i=1}^{n} C_i，求 \displaystyle\iint_{\Omega}(x^2+y^2)\,dxdy。

套用格林公式

将圆弧参数化，单段圆弧贡献为

其原函数可用

所以答案就是各段求和

朴素时间复杂度 \mathcal{O}(n^2)，容易做到 \mathcal{O}(n\log n)。

182. Cover the Polygon with Your Disk

Cover the Polygon with Your Disk

\color{cornflowerblue}{\textsf{Medium}}

求出一个圆 C 通过平移与凸包 P 的最大交集面积。

记 D 为 C,P 的闵可夫斯基差，f(\boldsymbol{t})=|(C+\boldsymbol{t})\cup P| 表示在平移 \boldsymbol{t} 后两者的交面积。f(\boldsymbol{t}) 在 D 上是单峰的，可以三分套三分求解极值。

对于三分中遇到 \boldsymbol{t} 不在 D 内的情况，用圆心与凸包的距离修正 f 以保证单峰性，可以正确求解。

时间复杂度 \mathcal{O}(n\log^2\epsilon^{-1})。

7350. Test For An Intern

Test For An Intern

\color{gold}{\textsf{Medium-Hard}}

求出一个凸包 Q 通过平移与凸包 P 的最大交集面积。

和上一题类似通过三分套三分求解，但是本题无法通过简单的修正来保证单峰性。本题的闵可夫斯基差 D 是平凡的，仍然是个凸包，因此在第一层三分到 x 时找到 x 与 D 相交的范围 y\in[l,r]，第二层直接在 [l,r] 上三分即可。

时间复杂度 \mathcal{O}(n\log n\log^2\epsilon^{-1})。

7310. Circular Sectors

Circular Sectors

\color{maroon}{\textsf{Very Hard}}

给出 n 个无特殊限制的扇形（i.e., 圆心可以不同、弧可以是优弧、边界可以重合），求出它们并集的面积。

这是一道偏重实现的题，思路很简单，只需要找到最终图形的边界然后用格林公式算一遍积分即可。

具体地说，先把图形做梯形/类梯形分解：

1. 对于半径边，把它分解为一个与 x 轴围成的梯形，判断它的下方是否在图形内然后确定梯形面积的正负；
2. 对于圆弧边，先把它过圆心水平切一刀，变成若干段沿着 x 轴单调的弧，然后判断每段弧分解成一个类梯形，同样需要判断面积的正负。

现在我们得到了至多 5n 个梯形，只需要求出每个梯形有多少部分在并集图形的边界上即可。不妨设当前的梯形在 x 位置的高度为 y_i(x)，梯形的符号为 t_i=\{-1,1\}，有若干段区间 x\in[l_j,r_j] 使得这段边界能够出现在图形上，那么这条边界的贡献就是:

线段 y(x)=kx+b 的积分是

圆弧 y(x)=c_y+\sigma\sqrt{r^2-(x-c_x)^2},\ \sigma=\{-1,1\} 的积分是

其中

问题变成计算边界裸露的位置，对每条边界讨论其他所有边界对它造成的遮挡，大概要分下面四种类型：

1. 线段 to 线段
2. 线段 to 圆弧
3. 圆弧 to 线段
4. 圆弧 to 圆弧

对于任意两段边界 p,q，求出 p 与 q 在 x 轴上的投影相交的位置，以及它们的交点。按照 x 轴排序可以得到若干段区间（圆弧可能产生两个交点）。对于每段区间 [l,r]：

1. - $p$ 和 $q$ 是同一个方向，该区间由编号较小的边界贡献； - $p$ 和 $q$ 不是同一个方向，可以直接 ban 掉；

最后，对 p 上的所有事件做扫描线，若一个区间没有被 ban 并且是括号平衡的，那么该区间就应该被计入贡献，进行积分即可。

时间复杂度 \mathcal{O}(n^2\log n)。

4369. Polygonal Puzzle

Polygonal Puzzle

\color{maroon}{\textsf{Very Hard}}

给两个多边形，可以平移旋转（但不能对称、缩放等），求这两个多边形贴在一起但不重合的情况下贴贴部分的最大总长度。

给一个不需要动脑的做法。记两个多边形分别为 P 和 Q。

首先，如果答案不为 0，那么至少会有一对边重合。在 P 和 Q 上各找一条边，求出这对边重合时的最长重合周长。将 P,Q 的对应边分别旋转平移到 x 轴的上下两侧，固定多边形 P，模拟 Q 从 x=-\infty 移动到 x=+\infty 的过程。

发现在移动的过程中会发生以下事件：

上述时刻只有 \mathcal{O}(n^2)个，重合周长的最大值一定在某个时刻取到。因此我们可以把 Q 平移到对应的 \mathcal{O}(n^2) 个位置上，然后判断在这个时刻 P,Q 两个多边形是否相交。

判多边形相交也可以暴力做：将 P,Q 三角剖分成 \mathcal{O}(n) 个三角形，然后我们再枚举 \mathcal{O}(n^2) 对三角形，判断两个三角形是否有交。

判断三角形交是简单的，比较稳妥的做法是把两个三角形的六条边的法向量当作轴，判断三角形的在该轴上的投影是否分离，存在分离则一定不相交，否则一定有交。这种判断方法的优势是在处理相交面积为 0 的情况下（边重合）精度较高，只需要算点乘。

做三角剖分需要判断一条边是否完全在多边形内，一个简单的做法是先枚举 \mathcal{O}(n^2) 条对角线，若与多边形边正规相交则该对角线不合法；若恰好有一个多边形的端点落在直线上，则递归下去查找，最后只需要判断一个线段的中点是否在多边形内。记忆化一下就是 \mathcal{O}(n^3) 的。知道了所有对角线的合法性后对多边形做耳分解即可。

综上，我们需要枚举 \mathcal{O}(n^2) 对边，做 \mathcal{O}(n^2) 个时刻的扫描线，再跑 \mathcal{O}(n^2) 的判断，总时间复杂度为 \mathcal{O}(n^6)。当然后两个 \mathcal{O}(n^2) 大概率跑不满，因此常数很小可以通过。

每次跑 \mathcal{O}(n^2) 的判断还是太慢了，其实有更聪明的办法，扩展一下扫描线的时刻：

可以发现重叠的边对于答案的贡献相当于是个分段线性函数，因此我们可以动态地维护若干个线性函数和的取值，最值点一定在上面的某个时刻取到。时刻总数依然是 \mathcal{O}(n^2) 的，需要对所有时刻进行排序，时间复杂度为 \mathcal{O}(n^4\log n)。

4111. 平凡的骰子

平凡的骰子

\color{gold}{\textsf{Medium-Hard}}

给定一个均质凸多面体骰子，随机抛掷后最终稳定在某一面上。以重心为球心作单位球面，每个面的着地概率等于该面在球面投影区域面积占全面积的比例。

求每个面着地的概率。

重心可以用混合积计算：将多边形拆分成若干个有向四面体，分别算出重心后加权。球面三角形的计算方式为 \alpha + \beta + \gamma - \pi；以此类推，球面多边形的面积就是 \sum_{i=1}^m\theta_i - (m-2)\pi。夹角 \theta_i 可以用法向量叉乘 + 反三角函数算出。

时间复杂度 \mathcal{O}(n)。

4677. Asteroids

Asteroids

\color{gold}{\textsf{Medium-Hard}}

给定两个凸多边形，每个凸多边形有一个初始位置和速度，在这个速度下做匀速运动。求出两个凸多边形在运动过程中的最大重合面积，或报告不会重合。

首先算出多边形发生相交的时间段 t\in [l,r]：先把两个凸包的运动转化成闵可夫斯基差的运动，求出与原点相交的时段，又等价于求一个射线与闵可夫斯基差的交。

记两个凸包在时刻 t 相交的面积为 f(t)，注意到 f(t) 在 [l,r] 上是单峰的，三分求出极值即可。优化精度和效率的方法：固定一个凸包让另一个凸包运动；用 convex cut 暴力求半平面交；三分时用黄金三分减少检查次数。

时间复杂度 \mathcal{O}(n^2\log \epsilon^{-1}) 或 \mathcal{O}(n\log n\log \epsilon^{-1})，取决于半平面交的实现。

11248. Convex Polyhedron

Convex Polyhedron

\color{gold}{\textsf{Medium-Hard}}

给定一个三维凸包，求一个平面使得三维凸包在这个平面上的投影面积最大。

首先枚举所有的可视面组合：枚举 n^3 个平面，求出其法向量 u，接着遍历三维凸包上的所有面并求其法向量 n_i，所有 u\cdot n_i > 0 的面都能被投影到同一个平面上。

接下来求出这些面能在同一个平面上投影出的最大面积：将所有面的单位法向量 n_i^{\ast} 按照面的面积加权平均，最后在该法向量上对应的平面投影即可。

时间复杂度 \mathcal{O}(n^4)。