[HDU 3007][最小覆蓋圓] Buried Memory

原題連結
嗚姆
今天來學最小覆蓋圓的隨機增量法，題目本身就是一個模板題QAQ。

教學
隨機增量法的作法本身並不難理解，只是當我發現複雜度是期望線性時我都驚呆了....

細節上要記得去把點打亂，否則特別構造的測資還是會讓時間爛掉的XD。

#define DB double
#include<cstdio>
#include<vector>
#include<cassert>
#include<algorithm>
using namespace std;
const DB eps=1e-7;
inline int dcmp(DB x)
{
    return abs(x)<eps?0:(x>0?1:-1);
}
struct Point
{
    DB x,y;
    Point() {}
    Point(DB _x,DB _y):x(_x),y(_y) {}
};
typedef Point Vector;
Vector operator + (const Vector& A,const Vector& B) {return Vector(A.x+B.x,A.y+B.y);}
Vector operator * (const Vector& A,const DB& t) {return Vector(A.x*t,A.y*t);}
Vector operator - (const Vector& A,const Vector& B) {return Vector(A.x-B.x,A.y-B.y);}
DB dis(const Point& A,const Point& B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
DB Cross(Vector A,Vector B) {return A.x*B.y-B.x*A.y;}
Point LineIntersec(Point& P,Vector& v,Point& Q,Vector& w)
{
    Vector u=P-Q;
    DB t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
Point get_center(const Point& A,const Point& B,const Point& C)
{
    Point P,v,Q,w;
    P=Point((A.x+B.x)/2.0,(A.y+B.y)/2.0);
    v=Vector(-(B.y-A.y),B.x-A.x);
    Q=Point((A.x+C.x)/2.0,(A.y+C.y)/2.0);
    w=Vector(-(C.y-A.y),C.x-A.x);
    return LineIntersec(P,v,Q,w); 
}
void get_radius(vector<Point> point)
{
    random_shuffle(point.begin(),point.end());
    
    Point center=Point(point[0].x,point[0].y);
    DB radius=0;
    int n=point.size();
    for(int i=1;i<n;i++)
    {
        if(dcmp(dis(point[i],center) - radius)<=0) continue;
        center=point[i];
        for(int j=0;j<i;j++)
        {
            if(dcmp(dis(point[j],center) - radius)<=0) continue;
            center.x= (point[i].x+point[j].x)/2.0;
            center.y= (point[i].y+point[j].y)/2.0;
            radius= dis(point[j],center);
            for(int k=0;k<j;k++)
            {
                if(dcmp(dis(point[k],center) - radius)<=0) continue;
                center= get_center(point[i],point[j],point[k]);
                radius= dis(point[k],center);
            }    
        }
    }
    printf("%.2f %.2f %.2f\n",center.x,center.y,radius);
}
int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        vector<Point> point;
        for(int i=0;i<n;i++)
        {
            Point p;
            scanf("%lf%lf",&p.x,&p.y);
            point.push_back(p);
        }
        get_radius(point);
    }
}