概述

给定n个点,求一最小圆覆盖所有的点,输出圆心坐标及半径。

随机增量法
假设当前圆O为前i-1个点的最小覆盖圆,加入第i个点若这个点不再圆内,则更新一个覆盖该点的最小圆,重复上述过程,由于三个点确定一个圆,因此我们在更新最小圆的时候在前i-1个点找两个点,与新点确定最小覆盖圆。

随机情况下,复杂度$O(n)$
证明,由于三点确定一个圆,因此新选出的点不在圆内的概率为$\frac{3}{i}$,期望为$O(n)$

模板

hdu3007

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 510;
const double eps = 1e-9;
struct Point{
double x,y;
} p[maxn];
int n;

double dis(Point& a,Point& b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

Point cal(Point& a,Point& b,Point& c)
{
Point res;
double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;
double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;
double d=a1*b2-a2*b1;
res.x=a.x+(c1*b2-c2*b1)/d;
res.y=a.y+(a1*c2-a2*c1)/d;
return res;
}

void solve(Point& res,double& r)
{
random_shuffle(p,p+n);
res = p[0]; r = 0;
for(int i=1;i<n;++i)
{
if(dis(res,p[i]) > r+eps)
{
res = p[i],r = 0;
for(int j=0;j<i;++j)
if(dis(res,p[j]) > r+eps)
{
res.x = (p[i].x+p[j].x)/2;
res.y = (p[i].y+p[j].y)/2;
r = dis(p[j],res);
for(int k=0;k<j;++k)
if(dis(res,p[k]) > r+eps)
{
res = cal(p[i],p[j],p[k]);
r = dis(p[i],res);
}
}
}
}
}


int main()
{
// freopen("test.txt","r",stdin);
while(~scanf("%d",&n) && n)
{
for(int i=0;i<n;++i) scanf("%lf %lf",&p[i].x,&p[i].y);
double r;
Point ans;
solve(ans,r);
printf("%.2lf %.2lf %.2lf\n",ans.x,ans.y,r);
}
return 0;
}