题目描述

给定 $ n $ 个点 (xi,yi)(x_i,y_i)，求半径最小的圆使该圆能覆盖所有的点。

所以这是一道最小覆盖圆的板子题，双倍经验：P1742

实现

使用随机增量法：

很容易我们能证明，若第 $ i $ 个点不在前 $ i-1 $ 个点的最小覆盖圆上，那么第 $ i $ 个点在前 $ i $ 个点的最小覆盖圆上。

这个时候，就要求前 $ i $ 个点的最小覆盖圆了。在初始化时，把圆心设为第 $ i $ 个点的坐标，半径设为 $ 0 $，强制使这个点在圆上。然后枚举就行了，如果当前这个点在当前这个圆外时就去求第 $ i $ 个点与该点在圆上时的最小覆盖圆，这个时候就要枚举除这两个点以外的第三个点（三点定圆）。枚举结束后就能求出前 $ i $ 个点的最小覆盖圆。

注意循环不用从 $ 1 $ 到 $ n $ 全部枚一遍，这样会造成重复枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=n;i++)
    if(!is_po_in_circle(a[i],c)){
        c=get_circ(0,a[i]);
        for(int j=1;j<=i-1;j++)
            if(!is_po_in_circle(a[j],c)){
                c.r=dist(a[i],a[j])/2;
                c.o.x=(a[i].x+a[j].x)/2;
                c.o.y=(a[i].y+a[j].y)/2;
                for(int k=1;k<=j-1;k++)
                    if(!is_po_in_circle(a[k],c))
                        c=get_circle_from_po(a[i],a[j],a[k]);
            }
    }

现在最大的问题来了：两点加直径定圆很简单，但是三点定圆有点难度，所以开始推式子：

假设两点 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2)，易得它们的中点是 (x1+x22,y1+y22)(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2})，经过它们的直线的斜率为 y1−y2x1−x2\frac{y_1-y_2}{x_1-x_2}。

因为三角形外接圆圆心（即外心）在在三条线段的中垂线上，故可知刚刚两个点的中垂线斜率为 −x1−x2y1−y2-\frac{x_1-x_2}{y_1-y_2}。再代入刚刚的中点，把式子化为 $ Ax+By+C=0$ 的形式，可知中垂线解析式为：

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

其他两条直线是一样的，联立求交点即可，这样圆心和半径都求出来了。

复杂度证明

这个看似时间复杂度是 $ O(n^3) $ 的做法实际上时间复杂度为 O(n)O(n)，证明如下：

由于所有点中，每次最多有 33 个点来确定最小覆盖圆，所以每次只有最多 3n\frac{3}{n} 的概率选到参与确定最小覆盖圆的点，即每个循环向下调用的概率不超过 3n\frac{3}{n}。

首先最后一层循环的复杂度是 O(j)O(j) 的，向上可以推得第二层的时间复杂度为：

O(i)+∑j=1i3iO(j)O(i)+\sum_{j=1}^i \frac{3}{i}O(j)

因为要经过随机排序，通过上面的式子容易得到这层的时间复杂度是 O(i)O(i)，那第一层的时间复杂度也显而易见是 O(n)O(n) 了。

AC 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
struct po{
    double x,y;
}; 
struct vec{
    double A,B,C;//Ax+By+C=0;
};
struct circ{
    po o;
    double r;
};
po a[2000001];
circ c;
vec get_vec_from_po(po p,po q){
    vec v;
    v.A=p.y-q.y;
    v.B=q.x-p.x;
    v.C=p.x*q.y-q.x*p.y;
    return v;
}
po get_po_from_vec(vec c,vec d){
    po pp;
    pp.x=((double)(-d.B*c.C+c.B*d.C)/(double)(-c.B*d.A+c.A*d.B));
    pp.y=((double)(-d.A*c.C+c.A*d.C)/(double)(c.B*d.A-c.A*d.B));
    return pp;
}
double dist(po a,po b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool is_po_in_circle(po test,circ d){
    return d.r>=sqrt((test.x-d.o.x)*(test.x-d.o.x)+(test.y-d.o.y)*(test.y-d.o.y));
}
circ get_circle_from_po(po A,po B,po C){
    vec buf1,buf2;
    buf1.A=2*(A.x-B.x),buf1.B=2*(A.y-B.y),buf1.C=B.x*B.x-A.x*A.x+B.y*B.y-A.y*A.y;
    buf2.A=2*(B.x-C.x),buf2.B=2*(B.y-C.y),buf2.C=C.x*C.x-B.x*B.x+C.y*C.y-B.y*B.y;
    circ temp;
    temp.o=get_po_from_vec(buf1,buf2);
    temp.r=dist(temp.o,A);
    return temp;
}
circ get_circ(double r,po o){
    circ temp_;
    temp_.r=r;
    temp_.o=o;
    return temp_;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    random_shuffle(a+1, a+n+1);
    for(int i=1;i<=n;i++)
        if(!is_po_in_circle(a[i],c)){
            c=get_circ(0,a[i]);
            for(int j=1;j<=i-1;j++)
                if(!is_po_in_circle(a[j],c)){
                    c.r=dist(a[i],a[j])/2;
                    c.o.x=(a[i].x+a[j].x)/2;
                    c.o.y=(a[i].y+a[j].y)/2;
                    for(int k=1;k<=j-1;k++)
                        if(!is_po_in_circle(a[k],c))
                            c=get_circle_from_po(a[i],a[j],a[k]);
                }
        }
    cout<<fixed<<setprecision(2)<<c.o.x<<" "<<c.o.y<<" ";
    cout<<fixed<<setprecision(2)<<c.r<<endl;
    return 0;
}