最小圆覆盖模板

几何算法

（1）加第1个点P1。C1的圆心就是P1，半径为0。

（2）加第二个点P2。新的C2的圆心是线段P1P2的中心，半径为两点距离的一半。这一步操作是两点定圆。 　　　　　

（3）加第三个点P3。若P3在圆内或圆上，忽略；若不在，则以P3为圆心，重复（1）和（2），若还是不行则用三点定圆。 　　　　　

（4）加第四个点P4。若P4在圆内或圆上，忽略；若不在，则以P4为圆心，从前三个点中选择一个点重复（1）和（2）即两点定圆，若还是不行则选三个点进行三点定圆(一定有)。 　　　　　

（5）继续加入新的点。

复杂度分析

3层for循环，貌似是O(n3)，但是当点的分布是随机的时候，可以通过概论计算得到实际复杂度接近O(n)，代码中使用random_shuffle()函数实现。

题目连接

点这里

AC代码

最小圆覆盖
struct Point {
    double x, y;
};

Point p[500005];
Point o;
int n;
double ri;

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

void tt(Point p1, Point p2, Point p3) {
    double a, b, c, d, e, f;
    a = p2.y - p1.y;
    b = p3.y - p1.y;
    c = p2.x - p1.x;
    d = p3.x - p1.x;
    f = p3.x * p3.x + p3.y * p3.y - p1.x * p1.x - p1.y * p1.y;
    e = p2.x * p2.x + p2.y * p2.y - p1.x * p1.x - p1.y * p1.y;
    o.x = (a * f - b * e) / (2 * a * d - 2 * b * c);
    o.y = (d * e - c * f) / (2 * a * d - 2 * b * c);
    ri = dis(o, p1);
}

int main() {
    while (scanf("%d", &n), n) {
        for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
        random_shuffle(p + 1, p + 1 + n);
        o = p[1];
        ri = 0;
        for (int i = 2; i <= n; i++) {
            if (dis(p[i], o) > ri + eps) {
                o = p[i], ri = 0;
                for (int j = 1; j <= i - 1; j++) {
                    if (dis(o, p[j]) > ri + eps) {
                        o.x = (p[i].x + p[j].x) / 2;
                        o.y = (p[i].y + p[j].y) / 2;
                        ri = dis(o, p[j]);
                        for (int k = 1; k <= j - 1; k++)
                            if (dis(o, p[k]) > ri + eps) tt(p[i], p[j], p[k]);
                    }
                }
            }
        }
        printf("%.2f %.2f %.2f\n", o.x, o.y, ri);
    }
}

tips

几何真就是知识盲区，这个真的就是tm的模板一套就会的东西，我居然写不出来哭~~