洛谷P1742 最小圆覆盖（计算几何 最小圆覆盖模板）

题目描述

给出N个点，让你画一个最小的包含所有点的圆。

输入格式

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

输出格式

输出圆的半径，及圆心的坐标，保留10位小数

输入输出样例

输入 #1复制

6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

输出 #1复制

5.0000000000
5.0000000000 5.0000000000

说明/提示

5.00 5.00 5.0

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int N = 1e5 + 5;

struct node
{
    double x, y;
}p[N];

node c; ///圆心
double r;   ///半径

int sgn(double x)
{
    if (fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

double Distance(node A, node B) ///两点距离
{
    return hypot(A.x - B.x, A.y - B.y); ///hypot(a, b)求以a, b为直角边的直角三角形斜边长
}

///求三角形abc的外接圆圆心
node circle_center(const node a, const node b, const node c)
{
    node center;
    double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    center.x = a.x + (c1 * b2 - c2 * b1) / d;
    center.y = a.y + (a1 * c2 - a2 * c1) / d;
    return center;
}

///求最小圆覆盖，返回圆心c和半径r:
void min_cover_circle(int n)
{
    random_shuffle(p, p + n);             ///打乱所有点
    c = p[0];
    r = 0;                    ///第一个点
    for (int i = 1; i < n; ++i)        ///剩下所有点
    {
        if (sgn(Distance(p[i], c) - r) > 0) ///pi在圆外部
        {
            c = p[i];
            r = 0;                ///将圆心设为pi半径为0
            for (int j = 0; j < i; ++j) ///重新检查前面的点
            {
                if (sgn(Distance(p[j], c) - r) > 0)///两点定圆
                {
                    c.x = (p[i].x + p[j].x) / 2;
                    c.y = (p[i].y + p[j].y) / 2;
                    r = Distance(p[j], c);
                    for (int k = 0; k < j; ++k)
                    {
                        if (sgn(Distance(p[k], c) - r) > 0)
                        {
                            c = circle_center(p[i], p[j], p[k]);
                            r = Distance(p[i], c);
                        }
                    }
                }
            }
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        min_cover_circle(n);
        printf("%.10f\n", r);
        printf("%.10f %.10f\n", c.x, c.y);
    }
    return 0;
}