BZOJ1337: 最小圆覆盖

题目：求n个点的最小圆覆盖。

题解：最小圆覆盖，上模板。复杂度证明可以戳：这里

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000000+5

 #define maxm 200000+5

 #define eps 1e-6

 #define ll long long

 #define ull unsigned long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)

 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)

 #define mod 1000000007

 #define lch k<<1,l,mid

 #define rch k<<1|1,mid+1,r

 #define sqr(x) (x)*(x)

 #define db double

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 struct point

 {

     db x,y;

     point operator +(point b){return (point){x+b.x,y+b.y};}

     point operator /(db b){return (point){x/b,y/b};}

 }a[maxn];

 int n;

 db ans;

 inline db dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

 inline point calc(db a,db b,db c,db d,db e,db f)

 {

   return (point){(c*e-f*b)/(a*e-d*b),(a*f-c*d)/(a*e-d*b)};

 }

 inline point get(point a,point b,point c)

 {

    return calc(b.x-a.x,b.y-a.y,(sqr(b.x)+sqr(b.y)-sqr(a.x)-sqr(a.y))/2.0,

         c.x-b.x,c.y-b.y,(sqr(c.x)+sqr(c.y)-sqr(b.x)-sqr(b.y))/2.0);

 }

 int main()

 {

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    n=read();

    for1(i,n)scanf("%lf%lf",&a[i].x,&a[i].y);

    for1(i,n)swap(a[rand()%n+],a[rand()%n+]);

    ans=;

    for1(i,n)if(dist(a[i],a[])>ans+eps)

    {

         a[]=a[i];ans=;

         for1(j,i-)if(dist(a[j],a[])>ans+eps)

         {

             a[]=(a[i]+a[j])/;ans=dist(a[],a[i]);

             for1(k,j-)if(dist(a[k],a[])>ans+eps)

             {

                 a[]=get(a[i],a[j],a[k]);ans=dist(a[],a[i]);

             }

         }

    }

    printf("%.2f %.2f %.2f\n",a[].x,a[].y,ans);

    return ;

 }

我不会说告诉你这题是三倍经验的