突然发现自己连这种经典模型都没做过,果然我还是太弱了qwq

最小圆覆盖就是用一个圆去覆盖平面上的一个点集,要求这个圆尽可能小。这个问题可以用随机增量法解决。

这个算法的流程是这样的:先把所有点random_shuffle一下,然后从前往后一个个加点。假设我们已经求出了$1\sim i-1$号点的最小圆覆盖(记为圆$C_{i-1}$),现在要求$C_i$。如果$i$号点在这个圆内(或圆上),则$C_i=C_{i-1}$。否则,我们可以确定$i$号点一定在$C_i$的边界上,且$C_i$的边界上最多只有$3$个点。如果出现了这种情况,我们就求一个子问题:覆盖了前$i-1$个点,且点$i$在边界上的最小的圆。

这个子问题的求法也类似,还是一个个加点。设当前加的点为$j$号点,我们已经得到了包含$1\sim j-1$且边界经过$i$号点的最小圆$C'_{j-1}$,现在要求$C'_j$。如果$j$号点在$C'_{j-1}$内,就可以跟之前一样令$C'_j=C'_{j-1}$。否则,我们可以确定$j$号点和$i$号点都在$C'_j$的边界上,然后又转化成了另一个子问题:覆盖了前$j-1$个点,且点$i$和$j$都在边界上的最小的圆。

这个子问题的求法也类似,还是一个个加点(怎么感觉这句话见过一次)。设当前加的点是$k$号点,我们已经得到了包含$1\sim k-1$且边界经过$j,i$号点的最小圆$C''_{k-1}$,现在要求$C''_k$。如果$k$号点在$C''_{k-1}$内,就可以跟之前一样令$C''_k=C''_{k-1}$。否则,我们可以确定$i,j,k$三个点都在$C''_k$的边界上。但是这时候就不用转化子问题了!因为三个点已经能确定一个圆了。。。

我们来分析一下这个算法的复杂度。记$T_1(n),T_2(n),T_3(n)$分别为三个子问题的复杂度。首先显然$T_3(n)=O(n)$,因为最多会求$n$次三点确定一个圆。由于点的顺序是随机的,且$C'_n$的边界上只会有$O(1)$个点,所以$n$号点在$C'_n$边界上的概率是$O(\frac 1n)$的。由此可得:

$$ \begin{aligned} T_2(n)&=T_2(n-1)+O(\frac 1n)T_3(n)\\&=T_2(n-1)+O(\frac 1n)O(n)\\&=T_2(n-1)+O(1)\\&=O(n) \end{aligned} $$

同理$T_1(n)=T_1(n-1)+O(\frac 1n)T_2(n)=O(n)$。所以整个算法的期望时间复杂度是线性的。

关于怎么三点确定一个圆,可以随便找两条边,然后算中垂线交点就行了(其实就是三角形的外心)。

具体实现的话可以看这道例题