zoj 1450 Minimal Circle(최소 포위 원)

Minimal Circle
Time Limit: 5 Seconds      
Memory Limit: 32768 KB
You are to write a program to find a circle which covers a set of points and has the minimal area. There will be no more than 100 points in one problem.
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
Source: 
Asia 1997, Shanghai (Mainland China)
제목: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
",o.x,o.y,r);
    }
    return 0;
}