最小圆覆盖

定义：

一个点集的最小圆覆盖是指可以将点集内的所有点覆盖的半径最小的圆。

随机增量法：

根据三个定点确定一个圆。

时间复杂度

1. 性质一：

描述：

一个点集的最小圆覆盖是唯一的。

证明：

如果有两个等大但不同的圆都可以将点集覆盖，那么这个点集的所有点一定在两个圆的交集部分。

那么以两个圆的交点连线为直径作圆，这个圆的直径一定小于之前的两个圆，且可以覆盖给定点集，与最小圆覆盖的定义矛盾。

所以一个点集的最小圆覆盖是唯一的。

2. 性质二：

描述：

如果一个点不在点集的最小圆覆盖内，那么点一定在点集的最小圆覆盖的边上。

证明：

作一个能包含点与点集中所有点的圆，那么点一定在圆外或圆上。

将圆缩小，最终一定可以缩成的最小圆覆盖，且原来的圆一定比这个圆大。

所以在缩小的过程中，一定会有经过点的时候，且这样的圆一定只有一个（证明同性质一）。

性质二得证。

算法描述：

for(i = 1; i <= n; i ++ )

若点不在点到构成的点集的最小圆覆盖内，则点一定在到构成的点集的最小圆覆盖上（性质二）。

for(j = 1; j < i; j ++ )

若点不在包含点到且点在边上的圆内，则点一定在包含点到且点在边上的最小圆上。

for(k = 1; k < j; k ++ )

若点不在包含点到且点和在边上的圆内，则点一定在包含点到且点和在边上的最小圆上。

此时一共确定个三个点，可以确定一个圆。

当时则有包含点到且点在边上的最小圆。

以此类推，就能确定点集到的最小圆覆盖。

code:

#include<cmath>
#include<random>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
const double eps = 1e-15;
const double Pi = acos(-1);

int sign(double x)
{
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}

int cmp(double a, double b)
{
    if(fabs(a - b) < eps) return 0;
    if(a > b) return 1;
    return -1;
}

int n;
struct vec {
    double x, y;
    
    vec operator- (const vec &t)const {return {x - t.x, y - t.y};}
    vec operator+ (const vec &t)const {return {x + t.x, y + t.y};}
    vec operator* (const double &t)const {return {x * t, y * t};}
    double operator^ (const vec &t)const {return x * t.y - t.x * y;}
    
} p[N];

struct line {
    vec p, v;
    
    vec intersection(const line &t)const 
    {
        vec u = t.p - p;
        
        double r = (u ^ t.v) / (v ^ t.v);
        return p + (v * r);
    }
};

struct circle {
    vec o;
    double r;
};

double get_dist(vec a, vec b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

vec rotate(vec v)
{
    double a = Pi / 2;
    double x = v.x * cos(a) + v.y * sin(a);
    double y = v.y * cos(a) - v.x * sin(a);
    return {x, y};
}

line get_line(vec a, vec b)
{
    vec st = (a + b) * 0.5;
    vec v = rotate(b - a);
    return {st, v};
}

circle get_circle(vec a, vec b, vec c)
{
    line v = get_line(a, b), u = get_line(b, c);
    vec o = v.intersection(u);
    return {o, get_dist(o, a)};
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%lf%lf", &p[i].x, &p[i].y);
    
    random_device rd;
    mt19937 gen(rd());
    shuffle(p + 1, p + 1 + n, gen); // 随机排序
    
    circle c = {p[1], 0};
    for(int i = 2; i <= n; i ++ )
    {
        if(cmp(c.r, get_dist(p[i], c.o)) < 0)
        {
            c = {p[i], 0};
            
            for(int j = 1; j < i; j ++ )
                if(cmp(c.r, get_dist(p[j], c.o)) < 0)
                {
                    c = {(p[i] + p[j]) * 0.5, get_dist(p[i], p[j]) / 2};
                    
                    for(int k = 1; k < j; k ++ )
                        if(cmp(c.r, get_dist(p[k], c.o)) < 0)
                            c = get_circle(p[i], p[j], p[k]);
                }
        }
    }
        
    
    printf("%.10lf\n", c.r);
    printf("%.10lf %.10lf\n", c.o.x, c.o.y);
    
    return 0;
}

firstlight's world