POJ 3932 Groundhog Build Home（最小圆覆盖） - c++编程基础

);
return ret;
}
Point Get_Rand(double X,double Y){
return Point((rand()%1000+1)/1000.0*X,(rand()%1000+1)/1000.0*Y);
}
int main(){
srand(time(NULL));
while(scanf("%lf%lf%d",&X,&Y,&n)!=EOF){
for(int i=0;i scanf("%lf%lf",&p[i].x,&p[i].y);
//随机20个点
for(int i=0;i tp[i]=Get_Rand(X,Y);
best[i]=Get_Dist(tp[i]);
}
double step=max(X,Y);
while(step>0.001){
for(int i=0;i pre=tp[i];
//走25步
for(int j=0;j<25;j++){
//随机一个方向
double angle=(rand()%1000+1)/1000.0*2*pi;
cur.x=pre.x+cos(angle)*step;

cur.y=pre.y+sin(angle)*step;
if(!cur.check()) continue;
double dis=Get_Dist(cur);
if(dis best[i]=dis;
tp[i]=cur;
}
}
}
//减小步长
step*=0.8;
}
double ans=inf;
int idx;
for(int i=0;i if(best[i] ans=best[i];
idx=i;
}
printf("(%.1f,%.1f).\n%.1f\n",tp[idx].x,tp[idx].y,ans);
}
return 0;
}

POJ 3932 Groundhog Build Home（最小圆覆盖）(二)