学步园

Input

The input contains several problems. The first line of each problem is a line containing only one integer N which indicates the number of points to be covered. The next N lines contain
N points. Each point is represented by x and y coordinates separated by a space. After the last problem, there will be a line contains only a zero.

Output

For each input problem, you should give a one-line answer which contains three numbers separated by spaces. The first two numbers indicate the x and y coordinates of the result circle,
and the third number is the radius of the circle. (use escape sequence %.2f)

Sample Input

2
0.0 0.0
3 0
5
0 0
0 1
1 0
1 1
2 2
0

Sample Output

1.50 0.00 1.50
1.00 1.00 1.41

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1450

题意：给你n个点，求一个最小的圆，能够包围这些点

分析：这题直接是模板题，不过我不会啊，最后找了好多资料，发现《计算几何--算法与应用》第4.7章里面讲得不错，也有证明。。。

模板直接抄袭某牛的= =

代码：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int mm=111;
typedef double diy;
struct point
{
    diy x,y;
}g[mm];
diy Sqr(diy x)
{
    return x*x;
}
diy Dis(point P,point Q)
{
    return sqrt(Sqr(P.x-Q.x)+Sqr(P.y-Q.y));
}
void Circle(point P0,point P1,point P2,point &o)
{
    diy a1=P1.x-P0.x,b1=P1.y-P0.y,c1=(Sqr(a1)+Sqr(b1))/2;
    diy a2=P2.x-P0.x,b2=P2.y-P0.y,c2=(Sqr(a2)+Sqr(b2))/2;
    diy d=a1*b2-a2*b1;
    o.x=P0.x+(c1*b2-c2*b1)/d;
    o.y=P0.y+(a1*c2-a2*c1)/d;
}
void MinCircle(point g[],point &o,diy &r,int n)
{
    random_shuffle(g,g+n);
    int i,j,k;
    o=g[0];
    for(r=0,i=1;i<n;++i)
    {
        if(Dis(g[i],o)<=r)continue;
        o=g[i];
        for(r=j=0;j<i;++j)
        {
            if(Dis(g[j],o)<=r)continue;
            o.x=(g[i].x+g[j].x)/2;
            o.y=(g[i].y+g[j].y)/2;
            r=Dis(o,g[i]);
            for(k=0;k<j;++k)
            {
                if(Dis(g[k],o)<r)continue;
                Circle(g[i],g[j],g[k],o);
                r=Dis(o,g[i]);
            }
        }
    }
}
int main()
{
    int i,n;
    point o;
    diy r;
    while(scanf("%d",&n),n)
    {
        for(i=0;i<n;++i)
            scanf("%lf%lf",&g[i].x,&g[i].y);
        MinCircle(g,o,r,n);
        printf("%.2lf %.2lf %.2lf\n",o.x,o.y,r);
    }
    return 0;
}