最小圆覆盖问题
jrxxx
·
·
算法·理论
---
[传送门](https://www.luogu.com.cn/problem/P1742)
给出 $n$ 个点的坐标，求一个最小直径的圆，使其能覆盖这 $n$ 个点。
$(1\le n\le 1e5)
随机增量法
最小圆覆盖的性质
性质1：最小圆覆盖是唯一的。
证明：反证法。
如图，假设两个圆 C_1,C_2 都是最小圆覆盖，且两圆交于点 A,B。
那么两圆重叠部分覆盖所有点。
则以 A,B 连线为直径作圆 C_3 （蓝色）一定覆盖所有点且 C_3 的直径小于 C_1,C_2。
与 C_1,C_2 是最小圆覆盖矛盾。
性质2：若点 A 在点集 P 的最小覆盖圆 C 外部，则 P\cup \{A\} 的最小覆盖圆 C' 过点 A。
只会显然 T_T。
性质3：最小覆盖圆一定是点集中三点所确定的或以两点连线为直径确定的。
只会显然 T_T。
算法思路
假设现在已经求出 i-1 个点的最小圆覆盖 C_{i-1}，考虑如何加入第 i 个点：
若第 i 个点在 C_{i-1} 内或圆周上，C_i=C_{i-1}；
否则 C_i 由第 i 个点和前 i-1 个点中的一个连线作为直径确定，或由第 i 个点和前 i-1 个点中的两个确定。
枚举即可。
具体地：
//伪代码
for(i=1;i<=n;++i)
{
if(p[i] in C[i-1]){C[i]=C[i-1];continue;}
init C[i]
for(j=1;j<i;++j)
{
if(p[j] in C[i]) continue;
C[i]=get(p[i],p[j]);//以i,j为直径两端点的圆
for(k=1;k<j;++k)
{
if(p[k] in C[i]) continue;
C[i]=get(p[i],p[j],p[k]);//过i,j,k三点的圆
}
}
}
随机因素的引入：将 n 个点 \text{random\_shuffle} 一下。
复杂度
一个圆最多由三个点确定，故每个点参与确定的概率最大为 \frac{3}{n}。
则每一层循环能进入下一层的概率最大为 \frac{3}{i}。
设三重循环复杂度为 T_1(n),T_2(n),T_3(n)。
则有
T_1(n)&=O(n)+\sum_{i=1}^n\frac{3}{i}\ T_2(i)\\
T_2(n)&=O(n)+\sum_{i=1}^n\frac{3}{i}\ T_3(i)\\
T_3(n)&=O(n)
\end{aligned}
解得：T_1(n)=T_2(n)=T_3(n)=O(n)。
实现细节
需要实现一个输入三点坐标，求外接圆的函数。
外接圆的性质：圆心为中垂线交点。
用点向式表示直线，点为连线中点，向为连线法向量。
$2$.已知两直线（点向式），求交点 $O$。
$l_1:(P_1,\boldsymbol v_1),\ l_2:(P_2,\boldsymbol v_2)$。
$O$ 在 $l_1$ 上，设 $O=P_1+\lambda \boldsymbol v_1$ 。
又 $O$ 在 $l_2$ 上：
$$
\begin{aligned}
|\overrightarrow{OP_2}\times \boldsymbol v_2|&=0\\
|(P_2-O)\times\boldsymbol v_2|&=0\\
|(P_2-P_1-\lambda \boldsymbol v_1)\times\boldsymbol v_2|&=0\\
\end{aligned}
$$
故 $\large \lambda=\frac{|(P_2-P_1)\times \boldsymbol v_2|}{|\boldsymbol v_1\times \boldsymbol v_2|}$ 。
代回可解得 $O$。
3.求半径。距离公式。
## 代码
```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#define db double
const int N=1e5+7;
struct vec
{
db x,y;
vec operator+(const vec a)const{return vec{x+a.x,y+a.y};}
vec operator-(const vec a)const{return vec{x-a.x,y-a.y};}
vec operator*(const db t)const{return vec{x*t,y*t};}
db operator*(const vec a)const{return x*a.x+y*a.y;}
db operator^(const vec a)const{return x*a.y-y*a.x;}
}p[N];
struct cir{vec o;db r;}C;
struct line{vec p,v;};
inline db dis(vec a,vec b){return hypot(a.x-b.x,a.y-b.y);}
inline vec mid(vec a,vec b){return vec{(a.x+b.x)/2,(a.y+b.y)/2};}
inline vec cross(line l1,line l2)
{
db t=((l2.p-l1.p)^l2.v)/(l1.v^l2.v);
return l1.p+l1.v*t;
}
inline bool in(vec v,cir c){return dis(v,c.o)<=c.r;}
inline cir get2(vec a,vec b){return cir{mid(a,b),dis(a,b)/2};}
inline cir get3(vec a,vec b,vec c)
{
line l1=line{mid(a,b),vec{b.y-a.y,a.x-b.x}};
line l2=line{mid(b,c),vec{b.y-c.y,c.x-b.x}};
vec o=cross(l1,l2);
return cir{o,dis(o,a)};
}
int main()
{
int n,i,j,k;
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
std::random_shuffle(p+1,p+n+1);
for(i=1;i<=n;++i)
{
if(in(p[i],C)) continue;
C=cir{p[i].x,p[i].y,0};
for(j=1;j<i;++j)
{
if(in(p[j],C)) continue;
C=get2(p[i],p[j]);
for(k=1;k<j;++k)
if(!in(p[k],C)) C=get3(p[i],p[j],p[k]);
}
}
printf("%.10lf\n%.10lf %.10lf",C.r,C.o.x,C.o.y);
return 0;
}
```
我就知道有人要嘴我用 $\text{random\_shuffle}$ /kk