求解计算几何中的最小圆覆盖问题
#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;
}