题解 P2533 【[AHOI2012]信号塔】

· · 题解

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

随机增量法

定理1：如果点pp不在集合SS的最小覆盖圆内，则pp一定在S\cup{p}S∪{p}的最小覆盖圆上。

根据这个定理，我们可以分三次确定前ii个点的最小覆盖圆。

1.令前i-1i−1个点的最小覆盖圆为CC

2.如果第ii个点在CC内，则前ii个点的最小覆盖圆也是CC

3.如果不在，那么第ii个点一定在前ii个点的最小覆盖圆上，接着确定前i-1i−1个点中还有哪两个在最小覆盖圆上。因此，设当前圆心为P_iP ，半径为0，做固定了第ii个点的前ii个点的最小圆覆盖。

4.固定了一个点：不停地在范围内找到第一个不在当前最小圆上的点Pj ，设当前圆心为(P_i+P_j)/2(P

5.固定了两个点：不停地在范围内找到第一个不在当前最小圆上的点P_kP k ​ ，设当前圆为P_i,P_j,P_kP i ​ ,P j ​ ,P k ​ 的外接圆。

所以就可以了！！！

代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const double eps = 1e-8;
struct Point {
    double x, y;
} a[N], O;
double R;
double sqr(double x) {return x * x;}
double dis(Point a, Point b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
void work(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);
    R = dis(O, p1);
}
int main() {
    int n, i, j, k;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);
    random_shuffle(a + 1, a + n + 1);
    O = a[1]; R = 0;
    for (i = 2; i <= n; ++i)
        if (dis(a[i], O) > R + eps) {
            O = a[i]; R = 0;
            for (j = 1; j < i; ++j)
                if (dis(a[j], O) > R + eps) {
                    O.x = (a[i].x + a[j].x) / 2; O.y = (a[i].y + a[j].y) / 2; R = dis(a[j], O);
                    for (k = 1; k < j; ++k) if (dis(a[k], O) > R + eps) work(a[i], a[j], a[k]);
                }
        }
    printf("%.2lf %.2lf %.2lf\n", O.x, O.y, R);
    return 0;
}