题解 P1742 【最小圆覆盖】

· · 题解

计算几何

前置知识：外接圆的求法

在初中我们就学过三点确定一个圆

这里我们首先考虑一下怎么求三角形的外接圆

我们考虑暴力解方程即可

利用圆的方程(x_1-x)^2+(y_2-y)^2=r^2

我们将三个点分别代进去可以得到三个方程

然后乱搞一下就能把x，y解出来了

这里给个式子

x=\frac{(x_2^2+y_2^2-x_1^2-y_1^2)(y_3-y_1)-(x_3^2+y_3^2-x_1^2-y_1^2)(y_2-y_1)}{2(x_2-x_1)(y_3-y_1)-2(x_3-x_1)(y_2-y_1)} y=\frac{(x_2^2+y_2^2-x_1^2-y_1^2)(x_3-x_1)-(x_3^2+y_3^2-x_1^2-y_1^2)(x_2-x_1)}{2(y_2-y_1)(x_3-x_1)-2(y_3-y_1)(x_2-x_1)}

我们就把外心坐标求出来了

具体做法

我们考虑暴力来解决这个问题

我们考虑假如我们已经有了i个点的最小圆覆盖

加入第i+1个点有两种情况

在圆内自然不要管

不在圆内，则该点一定在这i+1个点组成的最小圆覆盖上

因为前i个的最小圆覆盖并不包括第i+1个点

想要最小，圆一定过第i+1个点

接下来我们去枚举1~i-1的点j看点j是否能在目前构造出的1~i的最小圆覆盖内

不在，那么同上，点j一定在最小圆覆盖上

i与j构成一个新圆

接着枚举1~j-1的点k看点k是否在目前的1~i的最小圆覆盖内

不在，那么点k一定在最小圆覆盖上

三点确定一个圆，i，j，k的外接圆就是新的最小圆覆盖

为什么是正确的，由于三个点确定一个圆

而目前我们i，j，k都确定在目前1~i的最小圆覆盖上

那么这个圆就是最小圆覆盖

当k继续变大成l再一次不在这个圆内时

此时i，j，l三点一定在最小圆覆盖中，且小于l的点一定也在圆中

j的变大同理

时间复杂度证明

迷惑了！

当然不是 由于三点确定一个圆 **对于一个随机的序列，i个点每一个点有$\frac{3}{i}$的概率成为更新这些点的最小圆覆盖的点** 注意，这里并不是$\frac{3}{i}$的概率在圆上 因为影响我们复杂度的是它需要更新最小圆覆盖 那么对于进入第二重循环的if的概率应该是$\frac{3}{j}

那么第三重循环执行次数的期望应该是\frac{3}{j}*j=3

这是一个常数

那么第二重循环的总复杂度即为O(i)

对于进入第一重循环的if的概率同理，是\frac{3}{i}

那么进入if后的复杂度是O(\frac{3}{i}*i)=O(1)

故总期望复杂度为O(n)

注意上面的分析均为期望复杂度，故我们需要把点的顺序自己打乱，以免被卡

random_shuffle一下即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const double eps=1e-12;
struct point{
    double x,y;
}a[maxn];
int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*y;
}
double dis(point p,point q){
    double x=p.x-q.x,y=p.y-q.y;
    return sqrt(x*x+y*y);
}
point circle_center(point a,point b,point c){
    double x1=a.x,x2=b.x,x3=c.x;
    double y1=a.y,y2=b.y,y3=c.y;
    double A=x1*x1+y1*y1,B=x2*x2+y2*y2,C=x3*x3+y3*y3;
    double u1=x1-x2,u2=x1-x3,u3=x2-x3;
    double v1=y1-y2,v2=y1-y3,v3=y2-y3;
    point o;
    o.y=((C-A)*u1-(B-A)*u2)/(2*v1*u2-2*v2*u1);
    o.x=((C-A)*v1-(B-A)*v2)/(2*u1*v2-2*u2*v1);
    return o;
}
int main(){
    int n;
    n=read();
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    random_shuffle(a+1,a+n+1);
    point o=a[1];
    double r=0;
    for(int i=2;i<=n;i++){
        if(dis(o,a[i])-r>eps){
            o=a[i];r=0;
            for(int j=1;j<i;j++){
                if(dis(o,a[j])-r>eps){
                    o.x=(a[i].x+a[j].x)/2;
                    o.y=(a[i].y+a[j].y)/2;
                    r=dis(o,a[j]);
                    for(int k=1;k<j;k++){
                        if(dis(o,a[k])-r>eps){
                            o=circle_center(a[i],a[j],a[k]);
                            r=dis(o,a[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.10lf\n%.10lf %.10lf",r,o.x,o.y);
    return 0;
}