ZOJ1450 Minimal Circle 最小圆覆盖

ZOJ1450 给定N个点（N<=100）求最小的圆把这些点全部覆盖

考虑对于三角形，可以唯一的找到外接圆，而多边形又可以分解为三角形，所以对于多边形也可以找到唯一的最小覆盖圆。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const double eps=1e-10,PI=acos(-1.0);

int cmp(double k)
{
 return k<-eps ? -1:k>eps ? 1:0;
}

const double pi=acos(-1.0);

inline double sqr(double x)
{
 return x*x;
}






struct point
{
 double x,y;
 point (){}
 point (double a,double b):x(a),y(b){}
 bool input()
 	{
 	 return scanf("%lf%lf",&x,&y)!=EOF;
	}
 friend point operator +(const point &a,const point &b)
 	{
 	 return point(a.x+b.x,a.y+b.y);
	}	
 friend point operator -(const point &a,const point &b)
 	{
 	 return point(a.x-b.x,a.y-b.y);
	}
 friend bool operator ==(const point &a,const point &b)
 	{
 	 return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
	}
 friend point operator *(const point &a,const double &b)
 	{
 	 return point(a.x*b,a.y*b);
	}
 friend point operator*(const double &a,const point &b)
 	{
 	 return point(a*b.x,a*b.y);
	}
 friend point operator /(const point &a,const double &b)
 	{
 	 return point(a.x/b,a.y/b);
	}
 double norm()
 	{
 	 return sqrt(sqr(x)+sqr(y));
	}
};



void circle_center(point p0,point p1,point p2,point &cp)
{
 double a1=p1.x-p0.x,b1=p1.y-p0.y,c1=(a1*a1+b1*b1)/2.;
 double a2=p2.x-p0.x,b2=p2.y-p0.y,c2=(a2*a2+b2*b2)/2.;
 double d=a1*b2-a2*b1;
 cp.x=p0.x+(c1*b2-c2*b1)/d;
 cp.y=p0.y+(a1*c2-a2*c1)/d;
}

void circle_center(point p0,point p1,point &cp)
{
 cp.x=(p0.x+p1.x)/2.;
 cp.y=(p0.y+p1.y)/2;
}

bool point_in(const point &p,const point &c,const double r)
{
 return cmp((p-c).norm()-r)<=0;
} 

void min_circle_cover(point a[],int n,point &center,double &radius)
{
	radius=0;
	center=a[0];
	for(int i=1;i<n;i++)if(!point_in(a[i],center,radius))
							{
							 center=a[i];radius=0;
							 for(int j=0;j<i;j++)if(!point_in(a[j],center,radius)){
							 	circle_center(a[i],a[j],center);
							 	radius=(a[j]-center).norm();
							 	for(int k=0;k<j;k++)if(!point_in(a[k],center,radius)){
							 		circle_center(a[i],a[j],a[k],center);
							 		radius=(a[k]-center).norm();
								 }
							 }
							}
}
point pp[200];
int main()
{freopen("t.txt","r",stdin);
 int n;
 while(scanf("%d",&n)!=EOF&&n!=0)
 {
  for(int i=0;i<n;i++)pp[i].input();
  point cen;double r;
  min_circle_cover(pp,n,cen,r);
  printf("%.2lf %.2lf %.2lf
",cen.x,cen.y,r);
 }
 return 0;
}