「BZOJ1336 / 1337」[Balkan2002] Alien最小圆覆盖
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
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
5.00 5.00
HINT
用传说中的随机增量法，请自行百度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#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("%.10lf\n%.10lf %.10lf",r,o.x,o.y); //system("pause"); return 0; } |
计数器 9855357
OI 课件=>
OI 课件=>
我惊讶的发现我没写过随机增量