本文主要是介绍HDU 3932 Groundhog Build Home（最小圆覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3932
直接上模拟退火，不过我好像无法精准的掌握到精度啊？老是wa
代码：
#include<bits/stdc++.h>
using namespace std;
//hdu 3007 最小圆覆盖
namespace SA
{const double Lim=0.999999;//exp(-dif/T)为概率下降时候的阈值(或者可以用随机数)const double EPS=1e-3;const double PI=acos(-1.0);double Delta,maxx,minx,maxy,miny,lx,ly,dif;//Delta步长int n,ns,nc;//ns搜索点的个数，nc每次搜索每个点走的步数struct Point{double x,y;}P[1005];struct Solution{double x,y;double f;}S[25];double Dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}void Seed(){for(int i=1;i<=ns;i++){S[i].x=minx+((double)(rand()%1000+1)/1000.0)*lx;S[i].y=miny+((double)(rand()%1000+1)/1000.0)*ly;S[i].f=0.0;for(int j=1;j<=n;j++) S[i].f=max(S[i].f,Dis(S[i].x,S[i].y,P[j].x,P[j].y));}}void Trans(){for(int i=1;i<=ns;i++){for(int j=1;j<=nc;j++)//移动次数{Solution A;double theta=(((double)(rand()%1000+1))/1000.0)*2.0*PI;//退火的方向，有的题目里设定为八个方向A.x=S[i].x+Delta*cos(theta);A.y=S[i].y+Delta*sin(theta);if(A.x<minx||A.x>maxx||A.y<miny||A.y>maxy) continue;A.f=0.0;for(int k=1;k<=n;k++)A.f=max(A.f,Dis(A.x,A.y,P[k].x,P[k].y));dif=A.f-S[i].f;if(dif<0.0)S[i]=A;else{dif=exp(-dif/Delta);if(dif>Lim)S[i]=A;}}}}void solve(){minx=miny=0;for(int i=1;i<=n;i++){scanf("%lf%lf",&P[i].x,&P[i].y);}lx=maxx-minx;ly=maxy-miny;Delta=sqrt(lx*lx+ly*ly)/3.0;ns=1,nc=10;Seed();while(Delta>EPS){Trans();Delta=Delta*0.95;//0.95 0.9}int ans=1;for(int i=1;i<=ns;i++)if(S[ans].f>S[i].f)ans=i;printf("(%.1lf,%.1lf).\n%.1lf\n",S[ans].x,S[ans].y,S[ans].f);}
}
int main()
{while(~scanf("%lf%lf%d",&SA::maxx,&SA::maxy,&SA::n)&&SA::n){SA::solve();}return 0;
}这篇关于HDU 3932 Groundhog Build Home（最小圆覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
