bzoj 1336: [Balkan2002]Alien最小圆覆盖 随机增量法

bzoj 1336: [Balkan2002]Alien最小圆覆盖 随机增量法

题目大意：
求 n n n个点的最小圆覆盖。
n ≤ 1 0 5 n≤10^5 n≤105

分析：
就是使用随机增量法。
假如我们算出了前 i − 1 i-1 i−1个点的最小圆覆盖。
如果第 i i i个点在圆外，那么这个点一定在 i i i个点的最小圆覆盖内。
然后就是解决用一定包含这个点的圆覆盖前 i − 1 i-1 i−1个点的做法。
如果又遇到这种情况，相当于找一定包含这两个点的圆。
三层就结束了，因为三个点就已经确定了一个圆。

要先对输入的点随机打乱，这样也不会影响答案，而且可以防止被卡。
复杂度是 O ( n ) O(n) O(n)的。
这题要保留6位小数。

代码：

/**************************************************************Problem: 1336User: ypxrainLanguage: C++Result: AcceptedTime:420 msMemory:2856 kb
****************************************************************/#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>const int maxn=1e5+7;using namespace std;int n;
double r;struct rec{double x,y;
}a[maxn],cir;double getdis(rec a,rec b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}rec getmid(rec a,rec b)
{return (rec){(a.x+b.x)*0.5,(a.y+b.y)*0.5};
}rec getcen(rec a,rec b,rec c) 
{rec cen1=getmid(a,b);rec cen2=getmid(a,c);double k1,k2,b1,b2;if (a.y==b.y) {k2=-1.0/((c.y-a.y)/(c.x-a.x));b2=cen2.y-k2*cen2.x;return (rec){cen1.x,cen1.x*k2+b2};} if (a.y==c.y) {k1=-1.0/((b.y-a.y)/(b.x-a.x));b1=cen1.y-k1*cen1.x;return (rec){cen2.x,cen2.x*k1+b1};}k1=-1.0/((b.y-a.y)/(b.x-a.x));b1=cen1.y-k1*cen1.x;k2=-1.0/((c.y-a.y)/(c.x-a.x));b2=cen2.y-k2*cen2.x;return (rec){(b1-b2)/(k2-k1),k1*(b1-b2)/(k2-k1)+b1};
}int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);random_shuffle(a+1,a+n+1);cir=a[1],r=0;       for (int i=2;i<=n;i++){if (getdis(a[i],cir)>r){cir=a[i];r=0;for (int j=1;j<=i-1;j++){if (getdis(a[j],cir)>r){cir=getmid(a[j],a[i]);r=getdis(a[i],cir);for (int k=1;k<=j-1;k++){if (getdis(a[k],cir)>r){cir=getcen(a[i],a[j],a[k]);r=getdis(a[i],cir);}}}}}}   printf("%.6lfn",r);printf("%.6lf %.6lf",cir.x,cir.y);
}