93 lines
2.8 KiB
C++
93 lines
2.8 KiB
C++
#include <algorithm>
|
|
#include <cassert>
|
|
#include <cmath>
|
|
#include <cstdio>
|
|
#include <random>
|
|
const double EPS = 1e-10;
|
|
struct point {
|
|
double x, y;
|
|
inline point operator+(point rhs) const {
|
|
return (point){x + rhs.x, y + rhs.y};
|
|
}
|
|
inline point operator-(point rhs) const {
|
|
return (point){x - rhs.x, y - rhs.y};
|
|
}
|
|
inline point operator*(double rhs) const { return (point){x * rhs, y * rhs}; }
|
|
inline double len() const { return sqrt(x * x + y * y); }
|
|
};
|
|
inline int sgn(double x) {
|
|
if (x < -EPS) return -1;
|
|
if (x > EPS) return 1;
|
|
return 0;
|
|
}
|
|
inline double det(point x, point y) { return x.x * y.y - x.y * y.x; }
|
|
inline double dot(point x, point y) { return x.x * y.x + x.y * y.y; }
|
|
inline double dis(point x, point y) { return (x - y).len(); }
|
|
struct circle {
|
|
point c;
|
|
double r;
|
|
};
|
|
inline bool in_circle(point p, circle c) {
|
|
return sgn(c.r - (c.c - p).len()) >= 0;
|
|
}
|
|
inline circle make_circle(point x, point y) {
|
|
return (circle){(x + y) * 0.5, (x - y).len() * 0.5};
|
|
}
|
|
inline circle make_circle(point x, point y, point z) {
|
|
point p = y - x, q = z - x, s = (point){dot(p, p) * 0.5, dot(q, q) * 0.5};
|
|
double d = 1.0 / det(p, q);
|
|
p = (point){det(s, (point){p.y, q.y}), det((point){p.x, q.x}, s)} * d;
|
|
return (circle){x + p, p.len()};
|
|
}
|
|
inline circle get_circle(point x, point y, point z) {
|
|
if (sgn(det(y - x, z - x)) == 0) {
|
|
if ((x - y).len() >= (x - z).len()) {
|
|
if ((x - y).len() >= (y - z).len())
|
|
return make_circle(x, y);
|
|
else
|
|
return make_circle(y, z);
|
|
} else {
|
|
if ((x - z).len() >= (y - z).len())
|
|
return make_circle(x, z);
|
|
else
|
|
return make_circle(y, z);
|
|
}
|
|
} else
|
|
return make_circle(x, y, z);
|
|
}
|
|
using namespace std;
|
|
const int maxn = 1e5 + 10;
|
|
mt19937 rnd(random_device{}());
|
|
inline int rand_less(int n) { return rnd() % n; }
|
|
int n;
|
|
point pnt[maxn];
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%d", &n);
|
|
for (int i = 1; i <= n; i++) scanf("%lf%lf", &pnt[i].x, &pnt[i].y);
|
|
if (n == 2) {
|
|
printf("%.10lf\n", dis(pnt[1], pnt[2]) / 2);
|
|
printf("%.10lf %.10lf\n",((pnt[1]+pnt[2])*0.5).x,((pnt[1]+pnt[2])*0.5).y);
|
|
return 0;
|
|
}
|
|
random_shuffle(pnt + 1, pnt + 1 + n, rand_less);
|
|
circle cc = {pnt[1], 0};
|
|
// 注意：此处不要自作聪明地初始化，必须保证一定是真正的最小圆覆盖
|
|
for (int i = 2; i <= n; i++) {
|
|
if (in_circle(pnt[i], cc)) continue;
|
|
cc = make_circle(pnt[i], pnt[1]);
|
|
for (int j = 2; j <= i - 1; j++) {
|
|
if (in_circle(pnt[j], cc)) continue;
|
|
cc = make_circle(pnt[j], pnt[i]);
|
|
for (int k = 1; k <= j - 1; k++) {
|
|
if (in_circle(pnt[k], cc)) continue;
|
|
cc = get_circle(pnt[k], pnt[j], pnt[i]);
|
|
}
|
|
}
|
|
}
|
|
printf("%.10lf\n", cc.r);
|
|
printf("%.10lf %.10lf\n",cc.c.x,cc.c.y);
|
|
return 0;
|
|
} |