题解 P1742 最小圆覆盖：更详细的正确性证明

Ukraine · 2022-07-13 20:53:42 · 题解

这篇题解参考了讨论，并提供了较为详细的正确的证明。

记 \operatorname{circle}(S) 为点集 S 的最小圆覆盖，\operatorname{circum}(A,B,C) 为点 A,B,C 的外接圆。

引理 1

在二维平面上有 I,J,K,P 四个不同的点，那么以下两条互为充要条件：

• 存在 N,M\in \{I,J,K\} 且 N\neq M，使得 \operatorname{circle}(\{N,M,P\}) 包含这四个点。

引理 2

对于点集 S，如果 P\notin \operatorname{circle}(S)，那么 P 在 \operatorname{circle}(S\cup \{P\}) 上。

做法

我们考虑随机增量法：将点集随机打乱，从小到大枚举 i，如果 p_i\in\operatorname{circle}(\{p_1,p_2,\dots,p_{i-1}\})，那么前 i 个点的最小圆覆盖仍然是 \operatorname{circle}(\{p_1,p_2,\dots,p_{i-1}\})。否则，根据引理，p_i 一定在前 i 个点的最小圆上。所以，我们需要找到 j,k\in [1,i-1]，使得 \operatorname{circum}(p_k,p_j,p_i) 是前 i 个点的最小圆覆盖。

再从小到大枚举 1\le j<i，如果 j 不在当前的最小圆覆盖内，就先令当前最小圆为以 p_ip_j 为直径的圆，并枚举 1\le k<j，并查看 k 是否在当前的最小圆内，若不在则用 \operatorname{circum}(p_k,p_j,p_i) 作为当前的最小圆。

但如何保证更新一个最小圆后，这个圆仍然能够覆盖所有 1\dots i 的点？

假如原来的最小圆是 \operatorname{circum}(p_k,p_j,p_i)(k<j<i)，当最内层枚举了一个 k<k'<j，且 k' 不在当前最小圆上时，我们可以保证：

根据引理，可以得到：

归纳后得证。复杂度证明可以参考其他题解。

代码。

求两直线交点

记两条直线的方向向量分别是 \bm{d_1},\bm{d_2}，直线上一点的向量分别是 \overrightarrow{OP_1}=\bm{p_1},\overrightarrow{OP_2}=\bm{p_2}。

设交点的向量 \overrightarrow{OX}=\bm{p_1}+k\bm{d_1}，那么 (\overrightarrow{OX}-\bm{p_2})\times \bm{d_2}=0。

拆开得：