最小圆覆盖的相关概念

最小圆覆盖： 在二维平面上有若干个点，求一个最小的圆能将所有点都覆盖住，这就是最小圆覆盖问题，覆盖住所有点的最小的圆称为最小覆盖圆。

求最小圆覆盖问题：

首先可以得到一些性质。

性质 $1$：最小覆盖圆是唯一的。

假设存在两个半径都是最小的圆，且这两个圆不相同。由于这两个圆都能把所有点覆盖住，因此所有点的一定都在这两个圆的交集中，这个交集部分显然是一个对称图形，我们将交集部分的对称轴作为直径画一个圆，由于两个半径最小的圆不相同，因此交集部分的直径一定严格小于半径最小的圆的直径，那么此时我们沿着交集部分的直径画出的圆一定比那两个半径最小的圆更小，并且能把所有点覆盖住，这就与半径最小矛盾了，由此反证出最小覆盖圆是唯一的。

性质 $2$：假设我们已经求出了点集 $S$ 的最小覆盖圆，如果有一个点 $p$ 不在 $S$ 的最小覆盖圆内部，则 $p$ 一定在 $\lbrace p \rbrace \cup S$ 的最小覆盖圆的边上

我们假设 $p$ 不在 $S$ 的最小覆盖圆的边上，我们设 $S$ 的最小覆盖圆为 $c_1$，$\lbrace p \rbrace \cup S$ 的最小覆盖圆为 $c_2$，那么显然 $c_1 < c_2$，此时我们尝试将 $c_2$ 缩小，缩小的过程中时刻保证 $c_2$ 能覆盖 $S$ 中的所有点。最终 $c_2$ 一定会缩小成 $c_1$，在 $c_2$ 还没有缩小时，$p$ 在 $c_2$ 内部，当 $c_2$ 缩小成 $c_1$ 后，$p$ 在 $c_2$ 外部，因此在缩小的过程中必然存在一个中间的状态，使得 $p$ 在 $c_2$ 的边上，并且由于不存在两个相同的最小覆盖圆，因此 $c_2$ 在缩小的过程中直径一定也在缩小，这样我们就能构造出一个直径更小的覆盖圆，这与 $c_2$ 是最小覆盖圆矛盾了，由此反证出 $p$ 一定在最小覆盖圆的边上。

有了这两个性质，我们就可以去求最小覆盖圆了，我们如果能找出三个点必然在最小覆盖圆的边上，那么三个点能唯一确定一个圆，我们就能将最小覆盖圆找出来。

首先我们先将所有点随机排列，因为求最小覆盖圆的算法时间复杂度是建立在点完全随机的情况下的。

然后我们枚举每个点，依次将每个点加入到最小覆盖圆中，对于第一个点我们将他本身看作一个最小覆盖圆。对于每个点 $i$，如果在圆内，可以直接不用管，继续考虑下一个点。如果在圆外，那么我们将 $i$ 加入最小覆盖圆后，$i$ 一定在新的最小覆盖圆的边上，此时对于前 $i$ 个点的最小覆盖圆来说，我们已经确定了边上的一个点 $i$，接下来我们需要继续确定剩下的两个点。

由此此时我们保证 $i$ 一定在最小覆盖圆的边上，因此我们接下来只需要找所有 $i$ 在圆边上的圆，从最小的圆开始找，而 $i$ 这个点就是最小的一个 $i$ 在圆边上的圆，此时圆心就是 $i$，半径是 $0$，然后依次枚举 $1 \sim i-1$，假设我们现在已经求出来 $1 \sim j-1$ 都已经被覆盖，且 $i$ 在圆边上的最小覆盖圆，那么我们此时去将 $j$ 加入圆中，如果 $j$ 在圆内，那么 $1 \sim j$ 的最小覆盖圆就是 $1 \sim j-1$ 的最小覆盖圆，不用动，如果 $j$ 在圆外，那么此时 $j$ 一定在覆盖 $1 \sim j$ 且 $i$ 在边上的最小覆盖圆的边上。而我们用证明性质 $1$ 和性质 $2$ 的方法可以类似的证明出覆盖 $1 \sim j$ 且 $i,j$ 在边上的最小覆盖圆同样满足性质 $1$ 和性质 $2$。

此时我们已经找到圆上的两个点了，那么我们接下来就要找所有 $i,j$ 都在圆边上的最小覆盖圆，同样从最小的圆开始，也就是以 $i,j$ 为直径的圆。然后依次枚举 $1 \sim j-1$，假设我们现在已经求出来能覆盖 $1 \sim k-1$，并且 $j,i$ 都在边上的最小覆盖圆，然后我们要将 $k$ 加入圆中，如果 $k$ 在圆内，此时覆盖 $1 \sim k$ 的最小覆盖圆就是覆盖 $1 \sim k-1$ 的最小覆盖圆，不用管。如果 $k$ 在圆外，那么此时 $k$ 一定在覆盖 $1 \sim k$ 且 $i,j$ 都在边上的最小覆盖圆的边上。我们同样能用类似的方法证明出覆盖 $1 \sim k$ 且 $i,j,k$ 都在边上的最小覆盖圆是满足性质 $1$ 和性质 $2$ 的。

由于三点确定一个圆，那么我们现在就确定了能覆盖 $1 \sim k$ 且 $i,j,k$ 都在边上的最小覆盖圆，而当 $k=j-1$ 时，我们就能求出来能覆盖 $1 \sim j-1$ 且 $i,j$ 都在边上的最小覆盖圆，而我们第二层循环要求的是能覆盖 $1 \sim j$ 且 $i$ 在边上的最小覆盖圆，而他能递归到第三层循环就意味着 $j$ 必然也在圆边上，因此此时第三层循环求出来的圆其实就是第二层循环要求的圆。

而当 $j=i-1$ 时，我们就求出来了能覆盖 $1 \sim i-1$ 且 $i$ 在边上的最小覆盖圆，我们第一层循环要求的是覆盖 $1 \sim i$ 的圆，而能递归到第二层就意味着 $i$ 必然在圆的边上，因此此时第二层循环求出的圆就是第一层循环要求的圆，到此我们就求出了 $1 \sim i$ 的最小覆盖圆。当 $i=n$ 时，就求出了 $1 \sim n$ 的最小覆盖圆。

本题看似有三层循环，是 $O(n^3)$ 的复杂度，但是其实这个算法的期望时间复杂度是 $O(n)$ 的。首先第三层循环的时间复杂度是 $O(n)$ 的，但是第二层并不是所有情况都会往下循环，因为我们只需要三个点就能唯一确定一个圆，因此我们可以在环上选三个点作为关键点，如果我们没有枚举到关键点，其实是不会往下走的，因此我们只有 $\frac{3}{n}$ 的概率会走到内层循环，而我们最开始将所有点随机化，这更好的保证了随机性，因此第二层循环其实只有 $n+\frac{3}{n}O(n)$，因此第二层循环也是 $O(n)$ 的，同理第一层循环也是 $O(n)$ 的，所以整个算法的时间复杂度就是 $O(n)$ 的。

然后还需要考虑一下算法实现过程中的一些细节。把一个点看成一个圆，以及画一个两个点为直径的圆，这两个操作都比较好实现，但是我们还需要考虑如何去求三个点 $a,b,c$ 的外接圆，我们可以分别求一下 $ab$ 和 $ac$ 的中垂线，两个中垂线的交点就是圆心，圆心和圆上任意一点的距离就是半径。对于 $ab$ 的中垂线，由于中垂线一定是垂直的，所以中垂线的方向可以通过 $ab$ 顺时针旋转 $90^。$ 得到，如果用点向式表示直线，那么还需要一个中垂线的起点，可以取中垂线和 $ab$ 的交点，也就是 $ab$ 的中点，这样就将 $ab$ 的中垂线求出来了。同理 $ac$ 的中垂线也可以这样求出来，然后我们再求一下两个中垂线的交点，就是圆心，这样整个圆就求出来了。

这里再做一个扩展，我们已经能够求出最小覆盖圆了，那么最小覆盖球怎么求呢，三点确定一个圆，四点确定一个球，因此只需要在求最小覆盖圆的算法上再加一层循环求出四个点，就能求出最小覆盖球了。

可以发现实现过程中用到了很多计算几何的常用操作，这里可以参考 计算几何的基础知识