Description

给出N个点，让你画一个最小的包含所有点的圆。
Input

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)
Output

输出圆的半径，及圆心的坐标
Sample Input
6

8.0 9.0

4.0 7.5

1.0 2.0

5.1 8.7

9.0 2.0

4.5 1.0

Sample Output
5.00

5.00 5.00

最小圆覆盖模板，随机增量法。

最小覆盖圆， 增量法
假设圆O是前i-1个点得最小覆盖圆，加入第i个点，如果在圆内或边上则什么也不做。否,新得到的最小覆盖圆肯定经过第i个点。
然后以第i个点为基础（半径为0），重复以上过程依次加入第j个点，若第j个点在圆外，则最小覆盖圆必经过第j个点。
重复以上步骤（因为最多需要三个点来确定这个最小覆盖圆，所以重复三次）。遍历完所有点之后，所得到的圆就是覆盖所有点得最小圆。

证明可以考虑这么做：
最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可以通过这个思想得到。这个做法复杂度是O(n)的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是3/i,求出期望可得是O(n)。

//BZOJ 1336

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
const int maxn = 100010;
struct point{
    double x, y;
};
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
double getdis(point a, point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point center;
point get_circle_center(point a, point b, point c)//得到三角形外接圆圆心
{
    point center;
    double a1=b.x-a.x;
    double b1=b.y-a.y;
    double c1=(a1*a1+b1*b1)/2.0;
    double a2=c.x-a.x;
    double b2=c.y-a.y;
    double c2=(a2*a2+b2*b2)/2.0;
    double d=a1*b2-a2*b1;
    center.x=a.x+(c1*b2-c2*b1)/d;
    center.y=a.y+(a1*c2-a2*c1)/d;
    return center;
}
//p表示定点, n表示顶点的个数, c代表最小覆盖圆圆心, r是半径
void min_cover_circle(point *p, int n, point &c, double &r)//找最小覆盖圆(这里没有用全局变量p[], 因为是为了封装一个函数便于调用)
{
    random_shuffle(p, p + n);//随机函数,使用了之后使程序更快点,也可以不用
    c = p[0];
    r = 0;
    for (int i = 1; i < n; i++)
    {
        if (sgn(getdis(p[i], c) - r) > 0)//如果p[i]在当前圆的外面, 那么以当前点为圆心开始找
        {
            c = p[i];//圆心为当前点
            r = 0;//这时候这个圆只包括他自己.所以半径为0
            for (int j = 0; j < i; j++)//找它之前的所有点
            {
                if (sgn(getdis(p[j], c) - r) > 0)//如果之前的点有不满足的, 那么就是以这两点为直径的圆
                {
                    c.x = (p[i].x + p[j].x) / 2.0;
                    c.y = (p[i].y + p[j].y) / 2.0;
                    r = getdis(p[j], c);
                    for (int k = 0; k < j; k++)
                    {
                        if (sgn(getdis(p[k], c) - r) > 0)//找新作出来的圆之前的点是否还有不满足的, 如果不满足一定就是三个点都在圆上了
                        {
                            c = get_circle_center(p[i], p[j], p[k]);
                            r = getdis(p[i], c);
                        }
                    }
                }
            }
        }
    }
}
int n;
point p[maxn];

int main()
{
    scanf("%d", &n);
    point c;
    double r;
    for(int i=0; i<n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    min_cover_circle(p, n, c, r);
    printf("%.10f\n", r);
    printf("%.10f %.10f\n", c.x, c.y);
    return 0;
}