题解 P1742 【最小圆覆盖】

· · 题解

给出平面上 N 个点,N<=10^6，请求出一个半径最小的圆覆盖住所有的点，并求出该点的坐标与半径。

即经典的最小圆覆盖问题，在此我们介绍随机增量法：

随机增量法是一个可以在 期望O(n) 时间内求出最小圆覆盖的算法，首先它的算法流程是这样的

枚举第一个点 ii，若不在目前圆内，设它为圆心

枚举第二个点 jj，若不在当前圆内，设当前圆为以 i,ji,j 为直径的圆

枚举第三个点 kk，若不在当前圆内，设当前圆为 i,j,ki,j,k 的外接圆

正确性

显然最优解一定是两个点为直径的圆或者一个三角形的外接圆，否则肯定能缩的更小。那么这么枚举的正确性是比较显然的了

时间复杂度 这是一个重点，这么做看似是O(n^3)的，不过对于随机顺序的点，是可以期望 O(n)的。

但我可能不会证明！qwq

代码：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
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("%.10lf\n%.10lf %.10lf\n", R, O.x, O.y);
    return 0;
}