BZOJ 2823: [AHOI2012]信号塔 随机增量法

2823: [AHOI2012]信号塔

Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1063  Solved: 488 [Submit][Status][Discuss]

Description

在野外训练中，为了确保每位参加集训的成员安全，实时的掌握和收集周边环境和队员信息非常重要，集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息，这些传感器只与设在集训地中的信号塔进行通信，信号塔接收信号的覆盖范围是圆形，可以接收到所有分布在该集训区域内所有N个小型传感器（包括在该圆形的边上）发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比，因为是野外训练，只能使用事先储备好的蓄电设备，因此在可以收集所有传感器信息的基础上，还应使得信号塔的功率最小。小龙帮助教官确定了一种信号塔设置的方案，既可以收集到所有N个传感器的信号，又可以保证这个信号塔的功率是最小的。同学们，你们知道，这个信号塔的信号收集半径有多大，它应该设置在何处吗？

Input

共N+1行，第一行为正整数N（1≤N≤1000000），表示队员个数。接下来N行，每行两个实数用空格分开，分别是第i个队员的坐标X

Output

一行，共三个实数（中间用空格隔开），分别是信号塔的坐标，和信号塔 覆盖的半径。 （注：队员是否在边界上的判断应符合他到圆心的距离与信号塔接收半径之差的绝对值小于10^-6

Sample Input

5 1.200 1.200 2.400 2.400 3.800 4.500 2.500 3.100 3.900 1.300

Sample Output

2.50 2.85 2.10

HINT

1≤N≤500000

随机增量法求最小圆覆盖裸题

#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; typedef double db; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=501000,o=N-1; const db eps=1e-9; db x[N],y[N],r; inline db dis(int a,int b) {return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));} inline void geto(int a,int b,int c) { db a1,a2,b1,b2,c1,c2; a1=2*(x[b]-x[a]);b1=2*(y[b]-y[a]);c1=x[b]*x[b]-x[a]*x[a]+y[b]*y[b]-y[a]*y[a]; a2=2*(x[c]-x[a]);b2=2*(y[c]-y[a]);c2=x[c]*x[c]-x[a]*x[a]+y[c]*y[c]-y[a]*y[a]; if(abs(a1)<eps)y[o]=c1/b1,x[o]=(c2-y[o]*b2)/a2; else if(abs(b1)<eps)x[o]=c1/a1,y[o]=(c2-x[o]*a2)/b2; else x[o]=(c2*b1-c1*b2)/(a2*b1-a1*b2),y[o]=(c2*a1-c1*a2)/(b2*a1-b1*a2); } int a[N]; int main() { int n=read(); register int i,j,k; for(i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]),a[i]=i; random_shuffle(a+1,a+1+n); for(i=1;i<=n;++i)swap(x[a[i]],x[i]),swap(y[a[i]],y[i]); x[o]=x[1];y[o]=y[1];r=0; for(i=1;i<=n;++i) { if(dis(i,o)<r||abs(r-dis(i,o))<eps)continue; r=dis(i,1)/2;x[o]=(x[1]+x[i])/2;y[o]=(y[1]+y[i])/2; for(j=2;j<i;++j) { if(dis(j,o)<r||abs(r-dis(j,o))<eps)continue; r=dis(i,j)/2;x[o]=(x[i]+x[j])/2;y[o]=(y[i]+y[j])/2; for(k=1;k<j;++k) { if(dis(k,o)<r||abs(r-dis(k,o))<eps)continue; geto(i,j,k);r=dis(k,o); } } } printf("%.2lf %.2lf %.2lf\n",x[o],y[o],r); return 0; } /* 5 1.200 1.200 2.400 2.400 3.800 4.500 2.500 3.100 3.900 1.300 2.50 2.85 2.10 */