bzoj1336: [Balkan2002]Alien最小圆覆盖

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1336

1336: [Balkan2002]Alien最小圆覆盖

Time Limit: 1 Sec Memory Limit: 162 MBSec Special Judge
Submit: 1608 Solved: 713
[Submit][Status][Discuss]

Description

给出N个点，让你画一个最小的包含所有点的圆。

Input

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

Output

输出圆的半径，及圆心的坐标

Sample Input

6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

Sample Output

5.00
5.00 5.00

HINT

Source

最小圆覆盖裸题。

至于最小圆覆盖怎么写，看这篇博客吧，挺详细的http://blog.sina.com.cn/s/blog_6e63f59e010120dl.html

好久没写博客了……

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define maxn 100005

 using namespace std;

 int n;

 double r;

 const double eps=1e-;

 struct fuck{double x,y;}p[maxn],o;

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

 fuck operator -(fuck x,fuck y){return (fuck){x.x-y.x,x.y-y.y};}

 fuck operator *(fuck x,double y){return (fuck){x.x*y,x.y*y};}

 fuck operator /(fuck x,double y){return (fuck){x.x/y,x.y/y};}

 double sqr(double x){return x*x;}

 double dis(fuck x,fuck y){return sqr(x.x-y.x)+sqr(x.y-y.y);}

 void get(fuck x,fuck y,double &a,double &b,double &c){

     a=*(y.x-x.x);b=*(y.y-x.y);c=(sqr(x.x)+sqr(x.y)-sqr(y.x)-sqr(y.y));

 }

 void calc(double a,double b,double c,double d,double e,double f){

     o.y=(a*f-c*d)/(b*d-e*a);

     o.x=(b*f-c*e)/(a*e-b*d);

 }

 int main(){

     srand();

     scanf("%d",&n);

     for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);

     random_shuffle(p+,p+n+);

     o=p[];r=;

     for(int i=;i<=n;i++)if(dis(o,p[i])>r){

             o=p[i];r=;

             for(int j=;j<i;j++)if(dis(p[j],o)>r){

                     o=(p[j]+p[i])/;r=dis(p[j],o);

                     for(int k=;k<j;k++)if(dis(p[k],o)>r){

                         double a,b,c,d,e,f;

                         get(p[i],p[j],a,b,c);get(p[j],p[k],d,e,f);

                         calc(a,b,c,d,e,f);r=dis(o,p[k]);

                     }

                 }

         }

     printf("%f\n",sqrt(r));

     printf("%f %f\n",o.x,o.y);

 }

巴特西