普通的暴力复杂度达到O(n^4)，对于这题肯定是不行的。
解法：随机增量算法
参考http://www.2cto.com/kf/201208/149602.html
algorithm:
A、令Ci表示为前i个点的最小覆盖圆。当加入新点pi时如果pi不在Ci-1里那么pi必定在Ci的边界上。
B、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且p在Ci的的边界上！同理加入新点pi时如果p
i不在Ci-1里那么pi必定在Ci的边界上。这时我们就包含了两个点在这个最小圆的边界上。
C、再从新考虑这样一个问题，Ci为前i个点最小覆盖圆且有两个确定点再边界上！此时先让
O(N)的方法能够判定出最小圆。
------------------------------------------------------------------------------------
analysis:
现在来分析为什么是线性的。
C是线性的这是显然的。
B<-C的过程中。考虑pi 他在园内的概率为 (i-1)/i 。在圆外的概率为 1/i 所以加入pi的期望复杂度为：(1-i)/i*O(1) +(1/i)*O(i) {前者在园内那么不进入C，只用了O(1)。后者进入C用了O(i)的时间}这样分析出来，复杂度实际上仍旧
是线性的。
A<-B的过程中。考虑方法相同，这样A<-B仍旧是线性。于是难以置信的最小圆覆盖的复杂度变成了线性的。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 505
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x=,double y = ):x(x),y(y){}
}p[N];
typedef point pointt ;
pointt operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
point circumcenter(point a, point b, point c)
{ //返回三角形的外心
point ret;
double a1 = b.x-a.x,b1 = b.y-a.y,c1 = (a1*a1+b1*b1)/;
double a2 = c.x-a.x,b2 = c.y-a.y,c2 = (a2*a2+b2*b2)/;
double d = a1*b2-a2*b1;
ret.x=a.x+(c1*b2-c2*b1)/d;
ret.y=a.y+(a1*c2-a2*c1)/d;
return ret;
}
void min_cover_circle(point p[],int n,point &c,double &r)
{
random_shuffle(p,p+n);
c = p[],r = ;
int i,j,g;
for(i = ; i < n ;i++)
{
if(dcmp(dis(p[i]-c)-r)>)
{
c = p[i];
r = ;
for(j = ; j < i ; j++)
{
if(dcmp(dis(p[j]-c)-r)>)
{
c = point((p[i].x+p[j].x)/,(p[i].y+p[j].y)/);
r = dis(p[j]-c);
for(g = ; g < j; g++)
if(dcmp(dis(p[g]-c)-r)>)
{
c = circumcenter(p[i],p[j],p[g]);
r = dis(p[i]-c);
}
}
}
}
}
}
int main()
{
int n,i;
while(scanf("%d",&n)&&n)
{
for(i = ; i < n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
point c;
double r;
min_cover_circle(p,n,c,r);
printf("%.2f %.2f %.2f\n",c.x,c.y,r);
}
return ;
}
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 505
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x=,double y = ):x(x),y(y){}
}p[N];
typedef point pointt ;
pointt operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
point circumcenter(point a, point b, point c)
{ //返回三角形的外心
point ret;
double a1 = b.x-a.x,b1 = b.y-a.y,c1 = (a1*a1+b1*b1)/;
double a2 = c.x-a.x,b2 = c.y-a.y,c2 = (a2*a2+b2*b2)/;
double d = a1*b2-a2*b1;
ret.x=a.x+(c1*b2-c2*b1)/d;
ret.y=a.y+(a1*c2-a2*c1)/d;
return ret;
}
void min_cover_circle(point p[],int n,point &c,double &r)
{
random_shuffle(p,p+n);
c = p[],r = ;
int i,j,g;
for(i = ; i < n ;i++)
{
if(dcmp(dis(p[i]-c)-r)>)
{
c = p[i];
r = ;
for(j = ; j < i ; j++)
{
if(dcmp(dis(p[j]-c)-r)>)
{
c = point((p[i].x+p[j].x)/,(p[i].y+p[j].y)/);
r = dis(p[j]-c);
for(g = ; g < j; g++)
if(dcmp(dis(p[g]-c)-r)>)
{
c = circumcenter(p[i],p[j],p[g]);
r = dis(p[i]-c);
}
}
}
}
}
}
int main()
{
int n,i;
while(scanf("%d",&n)&&n)
{
for(i = ; i < n; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
point c;
double r;
min_cover_circle(p,n,c,r);
printf("%.2f %.2f %.2f\n",c.x,c.y,r);
}
return ;
}