Geometry / Numerical Methods tasks: Solution Set

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

Geometry / Numerical Methods tasks

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

14946. Collision Damage

Collision Damage

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

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

16202. 公园

公园

给定平面上 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。根据这条观察导出如下算法：

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

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

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

10105. Circular Parterre

Circular Parterre

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

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

详细版题解

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

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

9808. Fragile Pinball

Fragile Pinball

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

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

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

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

9037. Ancient Maps, Hidden Danger

Ancient Maps, Hidden Danger

给出 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

给出三维空间中的 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（逆时针）的外接圆的关系：

\mathsf{InCircle}(a,b,c,p)=\mathsf{sgn} \begin{vmatrix} a_x & a_y & a_x^2 + a_y^2 & 1 \\ b_x & b_y & b_x^2 + b_y^2 & 1 \\ c_x & c_y & c_x^2 + c_y^2 & 1 \\ p_x & p_y & p_x^2 + p_y^2 & 1 \end{vmatrix}

9728. Catch the Star

Catch the Star

给定 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

分类讨论。

9576. Ordainer of Inexorable Judgment

Ordainer of Inexorable Judgment

那维莱特。

9554. The Wheel of Fortune

The Wheel of Fortune

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

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

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

c^\prime = \dfrac{c\cdot S + p\cdot w}{S+w}

其中只有 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

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

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

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

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

7783. Military Maneuver

Military Maneuver

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

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

7734. Intersection over Union

Intersection over Union

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

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

5142. Grid Points

Grid Points

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

详细版题解

5104. Guardians of the Gallery

Guardians of the Gallery

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

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

详细版题解

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

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

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

1818. Apple Orchard

Apple Orchard

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

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

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

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

5067. Two Walls

Two Walls

在二维平面上，给定起点 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，另一侧的判断同理。整个过程需要判断线段相交，是否在端点相交，以及判断两点是否在线段的同一侧。判断都可以用叉乘表示，可以全整数运算。

10774. Monitored Area

Monitored Area

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

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

6612. A Bite of Teyvat

A Bite of Teyvat

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

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

5060. Circle

Circle

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

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

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

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

8019. Wowoear

Wowoear

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

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

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

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

2069. Geometry PTSD

Geometry PTSD

构造单位球面上的三个点 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

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

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

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

5046. Moon

Moon

单位球面上有固定点 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

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

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

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

2433. Panda Preserve

Panda Preserve

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

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

2767. Airport Construction

Airport Construction

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

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

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

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

4369. Polygonal Puzzle

Polygonal Puzzle

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

给一个不需要动脑的做法。记两个多边形分别为 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. 平凡的骰子

平凡的骰子

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

求每个面着地的概率。

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

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

4677. Asteroids

Asteroids

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

首先算出多边形发生相交的时间段 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})，取决于半平面交的实现。