$\huge{最小覆盖圆}$

$题意描述$

在一个平面上有 $n$ 个点，求一个半径最小的圆，能覆盖所有的点。

$过程$

假设圆 $O$ 是前 $i - 1$ 个点的最小覆盖圆，加入第 $i$ 个点，如果在圆内或边上则什么也不做。否则，新得到的最小覆盖圆肯定经过第 $i$ 个点。

然后以第 $i$ 个点为基础（半径为 $0$ ），重复以上过程依次加入第 $j$ 个点，若第 个点在圆外，则最小覆盖圆必经过第 $j$ 个点。

重复以上步骤。（因为最多需要三个点来确定这个最小覆盖圆，所以重复三次）

遍历完所有点之后，所得到的圆就是覆盖所有点得最小圆。

$性质$

时间复杂度 $O(n)$ 。

$实现$

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 100010;
const double eps = 1e-12, PI = acos(-1);
int n;
PDD q[N];

struct Circle {
    PDD p;
    double r;
};

PDD operator- (PDD a, PDD b)
{
    return {a.x - b.x, a.y - b.y};
}

PDD operator+ (PDD a, PDD b)
{
    return {a.x + b.x, a.y + b.y};
}

PDD operator* (PDD a, double t)
{
    return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t)
{
    return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b)
{
    return a.x * b.y - a.y * b.x;
}

PDD rotate(PDD a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

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

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

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}

pair<PDD, PDD> get_line(PDD a, PDD b)
{
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

Circle get_circle(PDD a, PDD b, PDD c)
{
    auto u = get_line(a, b), v = get_line(a, c);
    auto p = get_line_intersection(u.x, u.y, v.x, v.y);
    return {p, get_dist(p, a)};
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);
    random_shuffle(q, q + n);

    Circle c = {q[0], 0};
    for (int i = 1; i < n; i ++ )
        if (dcmp(c.r, get_dist(c.p, q[i])) < 0)
        {
            c = {q[i], 0};
            for (int j = 0; j < i; j ++ )
                if (dcmp(c.r, get_dist(c.p, q[j])) < 0)
                {
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2};
                    for (int k = 0; k < j; k ++ )
                        if (dcmp(c.r, get_dist(c.p, q[k])) < 0)
                            c = get_circle(q[i], q[j], q[k]);
                }
        }

    printf("%.10lf\n", c.r);
    printf("%.10lf %.10lf\n", c.p.x, c.p.y);

    return 0;
}