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

题意：给定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;
}