[AHOI2012]信号塔（最小圆覆盖）

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define db double
using namespace std;
const int N=1e6+10;
struct point
{
    db x,y;
}d[N],O;
db R;
int n;
db dis(point a,point b)
{
    db xx=a.x-b.x,yy=a.y-b.y;
    return sqrt(xx*xx+yy*yy);
}
bool in(point pos)
{
    if(dis(pos,O)<=R) return true;
    return false;
}
void get_O(point i,point j,point k)
{
    db a,b,c,d,e,f;
    a=j.x-i.x,b=j.y-i.y;
    c=k.x-j.x,d=k.y-j.y;
    e=j.x*j.x+j.y*j.y-i.x*i.x-i.y*i.y;
    f=k.x*k.x+k.y*k.y-j.x*j.x-j.y*j.y;
    O.x=(f*b-e*d)/(c*b-a*d)/2; 
    O.y=(a*f-e*c)/(a*d-b*c)/2;
    R=dis(O,i); 
}
void get_O(point a,point b)
{
    O.x=(a.x+b.x)/2;
    O.y=(a.y+b.y)/2;
    R=dis(a,b)/2;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&d[i].x,&d[i].y);
    O=d[1];
    for(int i=1;i<=n;i++)
    {
        if(in(d[i])) continue;
        O=d[i];
        for(int j=1;j<i;j++)
        {
            if(in(d[j])) continue;
            get_O(d[i],d[j]);
            for(int k=1;k<j;k++)
                if(!in(d[k])) get_O(d[i],d[j],d[k]);
        }
    }
    printf("%.2lf %.2lf %.2lf",O.x,O.y,R);
    return 0;
}