poj1379 模拟退火

题意：和上题一样。。。就是把最小值换成了最大值。。
ref：http://www.cppblog.com/RyanWang/archive/2010/01/21/106112.html
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<ctime>
  5 using namespace std;
  6 
  7 #define eps 1e-3
  8 #define pi  acos(-1.0)
  9 #define POI 15            //独立跑POI次，找最值        tp[1..POI]是随机的初值
 10 #define RUN 40            //迭代次数，本题中即点(tx,ty)向RUN个方向发散
 11 #define INF 99999.999
 12 int X,Y,N,T;
 13 double ans;
 14 int ansi;
 15 struct
 16 {
 17     double x,y;
 18 }tp[1010],hol[1010];
 19 double sol[1010];
 20 
 21 double dist(double x1,double y1,double x2,double y2)
 22 {
 23     return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
 24 }
 25 
 26 double dis(double x,double y)
 27 {
 28     double tmp=INF;
 29     for(int i=1;i<=N;i++)
 30     {
 31         double tx=hol[i].x,ty=hol[i].y;
 32         tmp=min(tmp,dist(tx,ty,x,y));
 33     }
 34     return tmp;
 35 }
 36 
 37 void sa()
 38 {
 39     for(int i=1;i<=POI;i++)
 40     {
 41         tp[i].x=(rand()%1000+1)/1000.0*X;
 42         tp[i].y=(rand()%1000+1)/1000.0*Y;
 43         sol[i]=dis(tp[i].x,tp[i].y);
 44         //printf("%.1f~%.1f=%.1f
",tp[i].x,tp[i].y,sol[i]);
 45     }
 46 
 47     double step=1.0*max(X,Y)/sqrt(1.0*N);
 48     while(step>eps)
 49     {
 50         for(int i=1;i<=POI;i++)
 51         {
 52             double kx=tp[i].x,ky=tp[i].y;
 53             double tx=kx,ty=ky;
 54             for(int j=0;j<RUN;j++)
 55             {
 56                 double angle=(rand()%1000+1)/1000.0*10*pi;
 57                 kx=tx+cos(angle)*step;
 58                 ky=ty+sin(angle)*step;
 59                 if((kx>X)||(ky>Y)||(kx<0)||(ky<0))    continue;
 60                 double tmp=dis(kx,ky);
 61                 if(tmp>sol[i])
 62                 {
 63                     tp[i].x=kx;    tp[i].y=ky;
 64                     sol[i]=tmp;
 65                 }
 66             }
 67         }
 68         step*=0.80;
 69     }
 70 }
 71 
 72 
 73 int main()
 74 {
 75     srand(time(NULL));
 76     cin>>T;
 77     //cout<<T<<endl;
 78     while(T--)
 79     {
 80         cin>>X>>Y>>N;
 81         for(int i=1;i<=N;i++)
 82             cin>>hol[i].x>>hol[i].y;
 83 
 84         sa();
 85 
 86         ans=0.000;    
 87         for(int i=1;i<=POI;i++)
 88         {
 89             //printf("AA: %.1f~%.1f=%.1f
",tp[i].x,tp[i].y,sol[i]);
 90             if(sol[i]>ans)
 91             {
 92                 ans=sol[i];
 93                 ansi=i;
 94             }
 95         }
 96         printf("The safest point is (%.1f, %.1f).
",tp[ansi].x,tp[ansi].y);
 97         //printf("%.1lf
",ans);
 98     }
 99     return 0;
100 }