题目链接
题解
最小圆覆盖模板
都懒得再写一次
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 1000005,maxm = 1000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct point{double x,y;}p[maxn],O;
int n;
double r;
double dis(const point& a,const point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double f(int i,int j,int k){
double a = p[j].y * p[j].y - p[i].y * p[i].y + p[j].x * p[j].x - p[i].x * p[i].x;
double b = p[k].y * p[k].y - p[j].y * p[j].y + p[k].x * p[k].x - p[j].x * p[j].x;
double c = p[j].y - p[i].y,d = p[k].y - p[j].y;
double e = 2 * (p[j].x - p[i].x) * d,ff = 2 * (p[k].x - p[j].x) * c;
return (a * d - b * c) / (e - ff);
}
double g(int i,int j,int k){
double a = p[j].y * p[j].y - p[i].y * p[i].y + p[j].x * p[j].x - p[i].x * p[i].x;
double b = 2 * (p[j].y - p[i].y);
double c = 2 * (p[j].x - p[i].x) * O.x;
return (a - c) / b;
}
void cal2(int u,int v){
O = (point){(p[u].x + p[v].x) / 2,(p[u].y + p[v].y) / 2};
r = dis(p[u],p[v]) / 2;
for (int i = 1; i < v; i++){
if (dis(p[i],O) <= r) continue;
O.x = f(u,v,i);
O.y = g(u,v,i);
r = sqrt((O.x - p[u].x) * (O.x - p[u].x) + (O.y - p[u].y) * (O.y - p[u].y));
}
}
void cal1(int u){
O = p[u]; r = 0;
for (int i = 1; i < u; i++){
if (dis(p[i],O) <= r) continue;
cal2(u,i);
}
}
void mincircle(){
O = p[1];
r = 0;
for (int i = 2; i <= n; i++){
if (dis(p[i],O) <= r) continue;
cal1(i);
}
}
int main(){
srand(time(NULL));
n = read();
for (int i = 1; i <= n; i++) scanf("%lf%lf",&p[i].x,&p[i].y);
random_shuffle(p + 1,p + 1 + n);
mincircle();
printf("%.2lf %.2lf %.2lf
",O.x,O.y,r);
return 0;
}