给定n个点，求一个最小的圆包围所有的点。

随机增量法

时间复杂度 O(n)

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;
const double eps = 1e-8;
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

typedef struct point{
    double x, y;
    point(){}
    point(double x, double y): x(x), y(y){}
    point operator+ (point p){return point(x+p.x, y+p.y);}
    point operator- (point p){return point(x-p.x, y-p.y);}
    point operator* (double k){return point(x*k, y*k);}
    point operator/ (double k){return point(x/k, y/k);}
}Vector;

point p[maxn];

double dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;}
double cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;}

point circumcenter(point a, point b, point c) {
    point A(b.x-a.x, c.x-a.x);
    point B(b.y-a.y, c.y-a.y);
    point C(dot(b+a, b-a)/2, dot(c+a, c-a)/2);
    return point(cross(C, B), cross(A, C)) / cross(A, B) + point(0, 0);
}

int point_in_crecle(point p, point c, double r) {
    return sgn(sqrt(dot(p-c, p-c)) - r);
}

void min_crecle(int n) {
    random_shuffle(p+1,p+n+1);
    point c(0, 0);
    double r = 0;
    for(int i = 1; i <= n; ++ i) {
        if (point_in_crecle(p[i], c, r) > 0) {
            c = p[i];
            r = 0;
            for(int j = 1; j < i; ++ j) {
                if (point_in_crecle(p[j], c, r) > 0) {
                    c = (p[i] + p[j]) / 2;
                    r = sqrt(dot(p[j]-p[i], p[j]-p[i])) / 2;
                    for(int k = 1; k < j; ++ k) {
                        if (point_in_crecle(p[k], c, r) > 0) {
                            c = circumcenter(p[i], p[j], p[k]);
                            r = sqrt(dot(p[i]-c, p[i]-c));
                        }
                    }
                }
            }
        }
    }
    printf("%-.10f\n%-.10f %-.10f\n", r, c.x, c.y);
}

int main() {
    int n; while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++ i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        min_crecle(n);
    }
    return 0;
}