大致题意:
平面上有n个点,求一个最小的圆覆盖住所有点
最小覆盖圆裸题
学习了一波最小覆盖圆算法
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<cstdlib>
#include<cmath>
#include<list>
using namespace std;
#define MAXN 100100
#define eps 1e-9
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Fore(i,a,b) for(int i=a;i>=b;i--)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mkp make_pair
#define pb push_back
#define cr clear()
#define sz size()
#define met(a,b) memset(a,b,sizeof(a))
#define iossy ios::sync_with_stdio(false)
#define fre freopen
#define pi acos(-1.0)
#define inf 1e6+7
#define Vector Point
const int Mod=1e9+;
typedef unsigned long long ull;
typedef long long ll;
int dcmp(double x){
if(fabs(x)<=eps) return ;
return x<?-:;
}
struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y) {}
bool operator < (const Point &a)const{
if(x==a.x) return y<a.y;
return x<a.x;
}
Point operator - (const Point &a)const{
return Point(x-a.x,y-a.y);
}
Point operator + (const Point &a)const{
return Point(x+a.x,y+a.y);
}
Point operator * (const double &a)const{
return Point(x*a,y*a);
}
Point operator / (const double &a)const{
return Point(x/a,y/a);
}
void read(){
scanf("%lf%lf",&x,&y);
}
void out(){
cout<<"debug: "<<x<<" "<<y<<endl;
}
bool operator == (const Point &a)const{
return dcmp(x-a.x)== && dcmp(y-a.y)==;
}
};
double Dot(Vector a,Vector b) {
return a.x*b.x+a.y*b.y;
}
double dis(Vector a) {
return sqrt(Dot(a,a));
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
int n;
Point p[];
double r;
Point cp;
bool inCrcle(Point tp){
return dcmp(dis(tp-cp)-r)<=;
}
void getCrcle(Point a,Point b,Point c){
Point p1=b-a,p2=c-a;
double d=*Cross(p1,p2);
cp.x=(p2.y*Dot(p1,p1)-p1.y*Dot(p2,p2))/d+a.x;
cp.y=(p1.x*Dot(p2,p2)-p2.x*Dot(p1,p1))/d+a.y;
r=dis(a-cp);
}
void solve(){
For(i,,n-) p[i].read();
random_shuffle(p,p+n);
cp=p[];r=;
For(i,,n-) {
if(!inCrcle(p[i])){
r=;
cp=p[i];
For(j,,i-) {
if(!inCrcle(p[j])) {
r=dis(p[j]-p[i])/;
cp=(p[j]+p[i])/;
For(k,,j-) {
if(!inCrcle(p[k]))
getCrcle(p[i],p[j],p[k]);
}
}
}
}
}
printf("%.2lf %.2lf %.2lf\n",cp.x,cp.y,r);
}
int main(){
// fre("in.txt","r",stdin);
int t=;
while(~scanf("%d",&n) && n) solve();
return ;
}