2823: [AHOI2012]信号塔

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1097  Solved: 498

[ ][ ][ ]

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

思路{随机增量法,第i个点在之前的点所构成的最小覆盖圆中的概率是3/i,那么易知这样打乱点的顺序暴力的方法是对的.}

 

#include
     
      #define RG register#define il inline#define db double#define LL long long#define N 1000010#define db doubleusing namespace std;struct point{  db x,y;  void read(){scanf("%lf%lf",&x,&y);}  point() {}  point(db X,db Y):x(X),y(Y) {}  point operator +(const point & a)const{return point(x+a.x,y+a.y);}  point operator -(const point & a)const{return point(x-a.x,y-a.y);}  point operator /(const db & k)const{return point(x/k,y/k);}  db operator *(const point & a)const{return x*a.y-y*a.x;}  db len(){return x*x+y*y;}}p[N];point getnode(point a,point b,point c){  point tmp;  point ab=b-a,ac=c-a;  db c1=ab.len()/2,c2=ac.len()/2;  db d=ab*ac;  tmp=point(a.x+(c1*ac.y-c2*ab.y)/d,a.y+(ab.x*c2-ac.x*c1)/d);  return tmp;}#define eps 1e-6int n;point c;db d;void work(){  random_shuffle(p+1,p+n+1);  c=p[1];d=0;  for(int i=2;i<=n;++i){    if((p[i]-c).len()>d-eps){      c=p[i];      d=0;      for(int j=1;j
      
       d-eps){      c=(p[j]+p[i])/2;      d=(p[j]-c).len();      for(int k=1;k
       
        d-eps){          c=getnode(p[i],p[j],p[k]);          d=(p[j]-c).len();        }    }    }  }}int main(){  scanf("%d",&n);  for(int i=1;i<=n;++i)p[i].read();  work();  printf("%.2lf %.2lf %.2lf",c.x,c.y,sqrt(d));  return 0;}