一直在我题单里没做掉 现在补一补:

题意:给定n个点,问最小的包含所有点的圆。输出半径及圆心位置。

解:

首先完全可以想到随机化的模拟退火,写起来也比较模板 这里不说了。

这道题的特点是可以用随机增量法

假设当前圆已经包含了前$i-1$个点,则第$i$个点要么在圆内要么在圆外。若在圆内则不用管他;在圆外的话,显然第i个点一定在前$i$个点的最小覆盖圆上。我们考虑一个暴力:首先找到包含前$i-1$个点的圆,加入第$i$个点,若$i$在圆内则无需操作,$i$在圆外则枚举前$i-1$个点中的两个点,使三个点确定的圆包含前$i$个点。

这样,显然最外层的枚举次数是$O(n)$的;若数据随机,则进入内层枚举的概率为$\frac{3}{i}$(因为i个点的最小覆盖圆可以只由3个在圆上的点确定)。总复杂度就为$O(n)+O(\sum_ { i=1 } ^ { n } \frac{3}{i}\cdot i^2)=O(n^2)$(我们假装:判断三个点是否能包含所有点这个操作是$O(1)$的)

如果上手写的话就会发现枚举这一步并不能做到$O(n^2)$。写的时候我们考虑先在外层(最外层我们已经想好了,不考虑了)枚举第二个点,用同样的思路,若前$j-1$个点与i点的覆盖圆已经包括了$j$点,那就不用管;若前$j-1$个点与$i$点的覆盖圆未包括j点,那$i$和$j$就是前$j$个点与$i$点的最小覆盖圆上的点,就需要继续开一层循环枚举第三个点。

我们来分析一下复杂度。一共三层循环,最外层$O(n)$,中层$O(\sum_ { i=1 } ^ { n } \frac{3}{i}\cdot i)=O(n)$,内层$O(\sum_ { i=1 } ^ { n } \frac{3}{i} \sum_ { j=1 } ^ { i-1 } \frac{3}{j} \cdot j)=O(n)$,故总复杂度是$O(n)$的。

其中还有一个计算几何的三点定圆的问题需要考虑

联立圆的方程可以列出共三元的三个方程,加减方程去掉变量$R$后对式子稍作移项变换,就形成了一个线性方程组。克拉默法则解出即可。但洛谷这题卡精度…long double即可(这里直接define了)

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
#define double long double
const int maxn=111111;
const double eps=1e-15;
struct Point
{
double x,y;
Point():x(0),y(0){}
Point(const double &xx,const double &yy):x(xx),y(yy){}
}point[maxn];
double sqr(const double &x){return x*x;}
double dis(Point &a,Point &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
Point getO(const Point &a,const Point &b,const Point &c)
{
Point res;
double xx=b.x-a.x,yy=b.y-a.y,XX=c.x-b.x,YY=c.y-b.y;
double d=sqr(b.x)+sqr(b.y)-sqr(a.x)-sqr(a.y),e=sqr(c.x)+sqr(c.y)-sqr(b.x)-sqr(b.y);
res.x=(e*yy-d*YY)/(XX*yy-xx*YY)/2;
res.y=(e*xx-d*XX)/(xx*YY-XX*yy)/2;
return res;
}
Point midpoint(const Point &x,const Point &y)
{
return Point((x.x+y.x)/2,(x.y+y.y)/2);
}
int n;
pair<double,Point> mincircle()
{
Point O=point[1];
double R=0;
rep(i,1,n)
{
if (dis(point[i],O)-R>eps)
{
O=point[i];
R=0;
rep(j,1,i-1)
{
if (dis(point[j],O)-R>eps)
{
O=midpoint(point[i],point[j]);
R=dis(point[i],point[j])/2;
rep(k,1,j-1)
{
if (dis(point[k],O)-R>eps)
{
O=getO(point[i],point[j],point[k]);
R=dis(point[i],O);
}
}
}
}
}
}
return make_pair(R,O);
}
int main()
{
read(n);
rep(i,1,n) scanf("%Lf%Lf",&point[i].x,&point[i].y);
srand(time(0));
random_shuffle(point+1,point+n+1);
pair<double,Point> ans=mincircle();
printf("%.10Lf\n%.10Lf %.10Lf\n",ans.first,ans.second.x,ans.second.y);
return 0;
}