最小圆覆盖问题

解题思路：

本题给定 $n$ 个点，要求一个能覆盖所有点的最小的圆，也就是一个求最小覆盖圆的模板题，直接套模板即可。

最小覆盖圆的相关概念可参考

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 100010;
const double eps = 1e-12;
const double PI = acos(-1);

struct Circle
{
    PDD p; //圆心
    double r; //半径
}; //圆

int n;
PDD q[N]; //存储所有点的坐标

int sign(double x) //符号函数
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

int dcmp(double x, double y) //浮点数比较函数
{
    if(fabs(x - y) < eps) return 0;
    if(x < y) return -1;
    return 1;
}

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) //将 a 顺时针旋转 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) //求 a 和 b 的距离
{
    double x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) //求两个点向式直线的交点
{
    PDD u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

pair<PDD, PDD> get_line(PDD a, PDD b) //求 ab 的中垂线
{
    return {(a + b) / 2, rotate(b - a, PI / 2)};
}

Circle get_circle(PDD a, PDD b, PDD c) //求出 a, b, c 的外接圆
{
    auto u = get_line(a, b), v = get_line(a, c);
    PDD 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}); //最开始圆只覆盖 p[0]
    for(int i = 1; i < n; i++) //枚举第一个点
        if(dcmp(c.r, get_dist(c.p, q[i])) < 0) //如果点 i 在圆外
        {
            c = {q[i], 0}; //从小到大枚举 q[i] 在边上的圆
            for(int j = 0; j < i; j++) //枚举第二个点
                if(dcmp(c.r, get_dist(c.p, q[j])) < 0) //如果点 j 在圆外
                {
                    c = {(q[i] + q[j]) / 2, get_dist(q[i], q[j]) / 2}; //从小到大枚举 q[i], q[j] 在边上的圆
                    for(int k = 0; k < j; k++) //枚举第三个点
                        if(dcmp(c.r, get_dist(c.p, q[k])) < 0) //如果点 k 在圆外
                            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;
}