[Balkan2002]Alien最小圆覆盖

[Balkan2002]Alien最小圆覆盖

[Balkan2002]Alien最小圆覆盖

Time Limit: 1 Sec Memory Limit: 162 MBSec Special Judge
Submit: 2592 Solved: 1129
[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

随机增量法求最小覆盖圆模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define eps 1e-8
using namespace std;
struct point{double x,y;}p[100005],o;
int n;
double r;
inline double sqr(double x){return x*x;}
inline double dis(point a,point b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
inline bool cmp(double a,double b)
{return fabs(a-b)<eps;}
point geto(point a,point b,point c)
{double a1,a2,b1,b2,c1,c2;point ans;a1=2*(b.x-a.x),b1=2*(b.y-a.y),c1=sqr(b.x)-sqr(a.x)+sqr(b.y)-sqr(a.y);a2=2*(c.x-a.x),b2=2*(c.y-a.y),c2=sqr(c.x)-sqr(a.x)+sqr(c.y)-sqr(a.y);if(cmp(a1,0)){ans.y=c1/b1;ans.x=(c2-ans.y*b2)/a2;}else if(cmp(b1,0)){ans.x=c1/a1;ans.y=(c2-ans.x*a2)/b2;}else{ans.x=(c2*b1-c1*b2)/(a2*b1-a1*b2);ans.y=(c2*a1-c1*a2)/(b2*a1-b1*a2);}return ans;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(int i=1;i<=n;i++)swap(p[rand()%n+1],p[rand()%n+1]);o=p[1];for(int i=1;i<=n;i++){if(dis(o,p[i])<r||cmp(dis(o,p[i]),r))continue;o.x=(p[i].x+p[1].x)/2;o.y=(p[i].y+p[1].y)/2;r=dis(p[i],p[1])/2;for(int j=2;j<i;j++){if(dis(o,p[j])<r||cmp(dis(o,p[j]),r))continue;o.x=(p[i].x+p[j].x)/2;o.y=(p[i].y+p[j].y)/2;r=dis(p[i],p[j])/2;for(int k=1;k<j;k++){if(dis(o,p[k])<r||cmp(dis(o,p[k]),r))continue;o=geto(p[i],p[j],p[k]);r=dis(o,p[i]);}}}printf("%.10lfn%.10lf %.10lf",r,o.x,o.y);//system("pause");return 0;
}