最小圆覆盖

Time Limit: 1 Sec  Memory Limit: 64 MB

Submit: 1464  Solved: 737

[][][]

Description

给出平面上N个点,N<=10^5.请求出一个半径最小的圆覆盖住所有的点

Input

第一行给出数字N，现在N行，每行两个实数x,y表示其坐标.

Output

输出最小半径，输出保留三位小数.

Sample Input

4

1 0

0 1

0 -1

-1 0

Sample Output

1.000

 

ac1() 模拟退火，ac2()随机增量法

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const double eps=1e-8; 9 const double INF=1e20; 10 const double PI=acos(-1.0); 11 12 13 ///pick定理：面积=内部格点数+（边上格点数/2）-1 14 15 int sgn(double x){ 16 if(fabs(x)
            
             0){142 c.p=p[i],c.r=0;143 for(int j=1;j
             
              0){145 c.p=(p[i]+p[j])/2;146 c.r=(c.p-p[j]).len();147 for(int k=1;k
              
               0){149 c=circle(p[i],p[j],p[k]);150 }151 }152 }153 }154 }155 }156 printf("%f\n%f %f\n",c.r,c.p.x,c.p.y);157 }158 159 double dist(Point a,Point b){160 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));161 }162 163 void ac1(){164 165 double ans=1e99;166 Point tmp;167 tmp.x=tmp.y=0;168 int s=1;169 double step=10000;170 double esp=0.000001;171 while(step>esp){172 for(int i=1;i<=n;i++){173 if(dist(tmp,p[s])