自动搬运

查看原文

来自洛谷，原作者为

	Ukraine **

搬运于2025-08-24 21:28:33，当前版本为作者最后更新于2022-07-13 20:53:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

引理 1

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

• $P$ 在 $\triangle IJK$ 外；
• 存在 $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'$ 不在当前最小圆上时，我们可以保证：

• $i\notin \operatorname{circum}(p_k,p_{k'},p_j)$；
• $j\notin \operatorname{circum}(p_k,p_{k'},p_i)$；
• $k'\notin \operatorname{circum}(p_k,p_j,p_i)$。

根据引理，可以得到：

$$k\in \operatorname{circum}(p_{k'},p_j,p_i).$$

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

代码。

求两直线交点

记两条直线的方向向量分别是 $\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$。

拆开得：

$$k=\frac{(\bm{p_2}-\bm{p_1})\times \bm{d_2}}{\bm{d_1}\times \bm{d_2}}. $$