最小圆覆盖问题

2024-08-14

求解计算几何中的最小圆覆盖问题

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 100001;
int sgn(double x)
{
    if (fabs(x) < EPS)
        return 0;
    else
        return x < 0 ? -1 : 1;
}
struct Point
{
    double x, y;
};
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); }
Point circle_center(const Point a, const Point b, const Point c)
{
    Point 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;
}
void min_cover_circle(Point *p, int n, Point &c, double &r)
{
    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)
        {
            c = p[i];
            r = 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);
                        }
                }
        }
}
Point p[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    Point c;
    double r;
    min_cover_circle(p, n, c, r);
    printf("%.10lf\n%.10lf %.10lf", r, c.x, c.y);
    return 0;
}