记录编号	106695	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1450]最小圆覆盖	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-06-18 09:51:25	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define sqr(x) (x)*(x)
const int SIZEN=110;
class POINT{
public:
	double x,y;
};
POINT P[SIZEN];
POINT O;//圆心
double R;
int N;
int random(int x,int y){
	return rand()%(y-x+1)+x;
}
void shuffle(void){
	for(int i=1;i<=N;i++) swap(P[i],P[random(i,N)]);
}
double dist(POINT a,POINT b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
POINT getcenter(POINT a,POINT b,POINT c){
	double a1,b1,c1,a2,b2,c2;//两条中垂线的方程
	a1=2.0*(a.x-b.x),b1=2.0*(a.y-b.y),c1=-sqr(a.x)-sqr(a.y)+sqr(b.x)+sqr(b.y);
	a2=2.0*(c.x-b.x),b2=2.0*(c.y-b.y),c2=-sqr(c.x)-sqr(c.y)+sqr(b.x)+sqr(b.y);
	POINT ans;
	ans.y=(a1*c2-c1*a2)/(b1*a2-a1*b2);
	ans.x=-(c1+b1*ans.y)/a1;
	return ans;
}
void work(void){
	O=P[1],R=0;
	for(int i=2;i<=N;i++){//这里把i加进去
		if(dist(O,P[i])>R){//那么i一定在圆上,确定圆上一个点i
			O=P[i],R=0;
			for(int j=1;j<i;j++){//这里把j加进去
				if(dist(O,P[j])>R){//那么j一定在圆上,确定圆上有i,j
					O.x=(P[i].x+P[j].x)/2.0;
					O.y=(P[i].y+P[j].y)/2.0;
					R=dist(O,P[i]);
					for(int k=1;k<j;k++){
						if(dist(O,P[k])>R){
							O=getcenter(P[i],P[j],P[k]);
							R=dist(O,P[i]);
						}
					}
				}
			}
		}
	}
	printf("%.8lf %.8lf %.8lf\n",O.x,O.y,R);
}
bool read(void){
	scanf("%d",&N);
	if(!N) return false;
	for(int i=1;i<=N;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
	return true;
}
int main(){
	freopen("minimalcircle.in","r",stdin);
	freopen("minimalcircle.out","w",stdout);
	srand(time(0));
	while(read()){
		shuffle();
		work();
	}
	return 0;
}