最小圆覆盖
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 #include2 #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])