hdu3932 模拟退火

模拟退火绝对是从OI--ACM以来接触过的所有算法里面最黑科技的orz

题意：地上有一堆hole，要找一个点，使得(距离该点最远的hole的距离)最小。

sol：本来想套昨天的模拟退火模板，初值(0,0)，向8个方向扩散。

然而这题并没有这么naive。

模板2.0 get：

 #define eps 1e-3
 #define pi  acos(-1.0)
 #define POI 15            //独立跑POI次，找其中最小的        tp[1..POI]是随机的初值
 #define RUN 40            //迭代次数，本题中即点(tx,ty)向RUN个方向发散

 void sa()
 {
     for(int i=;i<=POI;i++)
     {
         tp[i].x=(rand()%+)/1000.0*X;
         tp[i].y=(rand()%+)/1000.0*Y;
         sol[i]=dis(tp[i].x,tp[i].y);
         //printf("%.1f~%.1f=%.1f\n",tp[i].x,tp[i].y,sol[i]);
     }

     double step=1.0*max(X,Y)/sqrt(1.0*N);
     while(step>eps)
     {
         for(int i=;i<=POI;i++)
         {
             double kx=tp[i].x,ky=tp[i].y;
             double tx=kx,ty=ky;
             for(int j=;j<RUN;j++)
             {
                 double angle=(rand()%+)/1000.0**pi;
                 kx=tx+cos(angle)*step;
                 ky=ty+sin(angle)*step;
                 if((kx>X)||(ky>Y)||(kx<)||(ky<))    continue;
                 double tmp=dis(kx,ky);
                 if(tmp<sol[i])
                 {
                     tp[i].x=kx;    tp[i].y=ky;
                     sol[i]=tmp;
                 }
             }
         }
         step*=0.80;
     }
 }

AC Code：

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<ctime>
 using namespace std;

 #define eps 1e-3
 #define pi  acos(-1.0)
 #define POI 15            //独立跑POI次，找其中最小的        tp[1..POI]是随机的初值
 #define RUN 40            //迭代次数，本题中即点(tx,ty)向RUN个方向发散
 int X,Y,N;
 double ans;
 int ansi;
 struct
 {
     double x,y;
 }tp[],hol[];
 double sol[];

 double dist(double x1,double y1,double x2,double y2)
 {
     return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
 }

 double dis(double x,double y)
 {
     double tmp=0.000;
     for(int i=;i<=N;i++)
     {
         double tx=hol[i].x,ty=hol[i].y;
         tmp=max(tmp,dist(tx,ty,x,y));
     }
     return tmp;
 }

 void sa()
 {
     for(int i=;i<=POI;i++)
     {
         tp[i].x=(rand()%+)/1000.0*X;
         tp[i].y=(rand()%+)/1000.0*Y;
         sol[i]=dis(tp[i].x,tp[i].y);
         //printf("%.1f~%.1f=%.1f\n",tp[i].x,tp[i].y,sol[i]);
     }

     double step=1.0*max(X,Y)/sqrt(1.0*N);
     while(step>eps)
     {
         for(int i=;i<=POI;i++)
         {
             double kx=tp[i].x,ky=tp[i].y;
             double tx=kx,ty=ky;
             for(int j=;j<RUN;j++)
             {
                 double angle=(rand()%+)/1000.0**pi;
                 kx=tx+cos(angle)*step;
                 ky=ty+sin(angle)*step;
                 if((kx>X)||(ky>Y)||(kx<)||(ky<))    continue;
                 double tmp=dis(kx,ky);
                 if(tmp<sol[i])
                 {
                     tp[i].x=kx;    tp[i].y=ky;
                     sol[i]=tmp;
                 }
             }
         }
         step*=0.80;
     }
 }

 int main()
 {
     srand(time(NULL));
     while(cin>>X>>Y>>N)
     {
         for(int i=;i<=N;i++)
             cin>>hol[i].x>>hol[i].y;

         sa();

         ans=(X*X+Y*Y)*100.0;
         for(int i=;i<=POI;i++)
         {
             //printf("AA: %.1f~%.1f=%.1f\n",tp[i].x,tp[i].y,sol[i]);
             if(sol[i]<ans)
             {
                 ans=sol[i];
                 ansi=i;
             }
         }
         printf("(%.1f,%.1f).\n",tp[ansi].x,tp[ansi].y);
         printf("%.1lf\n",ans);
     }
     return ;
 }

ref：

http://blog.****.net/acm_cxlove/article/details/7954321

http://blog.****.net/zxy_snow/article/details/6682926

http://www.kuangbin.net/archives/hdu3932#more-435