随机增量算法 - 最小圆覆盖

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps = 1e-8;
const db pi = acos(-1.0);
const ll maxn = 1e5 + 10;

inline int dcmp(db x) {
    if(fabs(x) < eps) return 0;
    return x > 0? 1: -1;
}

class Point {
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    bool operator<(const Point &a) const {
        return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x;
    }
    bool operator==(const Point &a) const {
        return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
    }
    db dis2(const Point a) {
        return pow(x - a.x, 2) + pow(y - a.y, 2);
    }
    db dis(const Point a) {
        return sqrt(dis2(a));
    }

    db dis2() {
        return x * x + y * y;
    }
    db dis() {
        return sqrt(dis2());
    }
    Point operator+(const Point a) {
        return Point(x + a.x, y + a.y);
    }
    Point operator-(const Point a) {
        return Point(x - a.x, y - a.y);
    }
    Point operator*(double p) {
        return Point(x * p, y * p);
    }
    Point operator/(double p) {
        return Point(x / p, y / p);
    }
    db dot(const Point a) {
        return x * a.x + y * a.y;
    }
    db cross(const Point a) {
        return x * a.y - y * a.x;
    }
    db ang(Point a) {
        return acos((a.dis() * dis()) / dot(a));
    }
};
typedef Point Vector;

class Circle {
public:
    Point o;
    db r;
    Circle() {}

    // 点和半径
    Circle(Point o, db r):o(o), r(r){}

    // 三点定圆
    Circle(Point A, Point B, Point C) {
        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;
        o.x = A.x + (c1 * b2 - c2 * b1) / d;
        o.y = A.y + (a1 * c2 - a2 * c1) / d;
        r = o.dis(A);
    }
    Point point(db a) {
        return Point(o.x + cos(a) * r, o.y + sin(a) * r);
    }
    // 点在圆内
    bool PinC(Point p) {
        db d = p.dis(o);
        return dcmp(d - r) < 0;
    }
    // 点在圆外
    bool PoutC(Point p) {
        db d = p.dis(o);
        return dcmp(d - r) > 0;
    }
};

vector<Point> p;

// 最小圆覆盖
Circle min_circle(vector<Point> p) {
    int sz = p.size();
    // 随机点
    random_shuffle(p.begin(), p.end());

    Circle ans(p[0], 0.0);

    for(int i = 0; i < sz; ++i) {
        // 如果点在圆外，则用外面这个点作为新的半径
        if(ans.PoutC(p[i])) {
            ans = Circle(p[i], 0);
            
            for(int j = 0; j < i; ++j) {
                if(ans.PoutC(p[j])) {
                    // 找到2个点的圆
                    ans = Circle((p[i] + p[j]) / 2.0, p[i].dis(p[j]) / 2.0);
                    for(int k = 0; k < j; ++k) {
                        if(ans.PoutC(p[k])) {
                            // 找到3个点的圆
                            ans = Circle(p[i], p[j], p[k]);
                        }
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    // 输入n个点
    for(int i = 0; i < n; ++i) {
        Point tmp;
        tmp.input();
        p.push_back(tmp);
    }

    // 通过点集计算最小的圆
    Circle ans = min_circle(p);

    printf("%.10lf\n%.10lf %.10lf\n", ans.r, ans.o.x, ans.o.y);
    return 0;
}