HDU 3007 Buried memory （最小圆覆盖，随机增量法）

题目传送门

求覆盖 n 个点的最小圆

时间复杂度：o（n）

推荐博客：

博客1

博客2

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF INT_MAX
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
using namespace std;

const int N = 522;
const LL mod = 1e9 + 7;
const double eps = 1e-8;

double X, Y;

struct Point {
    double x, y;
}p[N];

struct Triangle {
    Point v[3];
};

struct Circle {
    Point center;
    double r;
};

double pow(double x) {
    return x * x;
}

double Len(Point a, Point b) {
    return sqrt(pow(a.x - b.x) + pow(a.y - b.y));
}

double TriangleArea(Triangle a) { /// 求三角形的面积
    double px1 = a.v[1].x - a.v[0].x;
    double py1 = a.v[1].y - a.v[0].y;
    double px2 = a.v[2].x - a.v[0].x;
    double py2 = a.v[2].y - a.v[0].y;
    return fabs(px1 * py2 - px2 * py1) / 2;
}

Circle CircleOfTriangle(Triangle t) { /// 求三角形外接圆
    Circle tmp;

    double a = Len(t.v[0], t.v[1]);
    double b = Len(t.v[0], t.v[2]);
    double c = Len(t.v[1], t.v[2]);

    tmp.r = a * b * c / 4 / TriangleArea(t);

    double a1 = t.v[1].x - t.v[0].x;
    double b1 = t.v[1].y - t.v[0].y;
    double c1 = (a1 * a1 + b1 * b1) / 2;

    double a2 = t.v[2].x - t.v[0].x;
    double b2 = t.v[2].y - t.v[0].y;
    double c2 = (a2 * a2 + b2 * b2) / 2;

    double d = a1 * b2 - a2 * b1;

    tmp.center.x = t.v[0].x + (c1 * b2 - c2 * b1) / d;
    tmp.center.y = t.v[0].y + (a1 * c2 - a2 * c1) / d;

    return tmp;
}
void Run(int n) {

    random_shuffle(p + 1, p + n + 1); /// 随机排序取点

    Circle tep;
    tep.center = p[1];
    tep.r = 0;

    rep(i, 2, n) {
        if(Len(p[i], tep.center) > tep.r + eps) {
            tep.center = p[i];
            tep.r = 0;
            rep(j, 1, i - 1) {
                if(Len(p[j], tep.center) > tep.r + eps) {
                    tep.center.x = (p[i].x + p[j].x) / 2;
                    tep.center.y = (p[i].y + p[j].y) / 2;
                    tep.r = Len(p[i], p[j]) / 2;
                    rep(k, 1, j - 1) {
                        if(Len(p[k], tep.center) > tep.r + eps) {
                            Triangle t;
                            t.v[0] = p[i];
                            t.v[1] = p[j];
                            t.v[2] = p[k];
                            tep = CircleOfTriangle(t);
                        }
                    }
                }
            }
        }
    }

    printf("%.2f %.2f %.2f
",tep.center.x,tep.center.y,tep.r);

}

int main() {

    int n;

    while(scanf("%d",&n),n) {

        rep(i, 1, n) scanf("%lf%lf",&p[i].x,&p[i].y);

        Run(n);

    }
    return 0;

}