1 //Accepted    220 KB    829 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <ctime> 6 #include <cstdlib> 7 #include <iostream> 8 using namespace std; 9 const int iL=30;10 const int iP=30;11 const double inf=10000000.0;12 const double Pi=acos(-1.0);13 int n;14 int T;15 double boundary_x,boundary_y;16 int cnt;17 double hole_x[1005],hole_y[1005];18 double x[iP],y[iP],dis[iP];19 double min(double a,double b)20 {21     if (a-b<1e-12)22     return a;23     return b;24 }25 double get_dis(double x1,double y1,double x2,double y2)26 {27     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));28 }29 void sa()30 {31     srand(time(NULL));32     for (int i=0;i<iP;i++)33     {34         x[i]=double(rand()%1000+1)/1000.0*boundary_x;35         y[i]=double(rand()%1000+1)/1000.0*boundary_y;36         dis[i]=inf;37         for (int j=0;j<cnt;j++)38         {39             if (dis[i]>get_dis(x[i],y[i],hole_x[j],hole_y[j]))40             dis[i]=get_dis(x[i],y[i],hole_x[j],hole_y[j]);41         }42     }43     double delta=sqrt(boundary_x*boundary_x+boundary_y*boundary_y);44     while (delta>0.0001)45     {46         for (int i=0;i<iP;i++)47         {48             double temp_x=x[i],temp_y=y[i],temp_dis=dis[i];49             for (int j=0;j<iL;j++)50             {51                 double theta=double(rand()%1000+1)/1000.0*2*Pi;52                 double nx=x[i]+delta*cos(theta);53                 double ny=y[i]+delta*sin(theta);54                 if (nx<0 || nx>boundary_x || ny<0 || ny>boundary_y)55                 continue;56                 double ndis=inf;57                 for (int k=0;k<cnt;k++)58                 ndis=min(ndis,get_dis(nx,ny,hole_x[k],hole_y[k]));59                 if (ndis>temp_dis)60                 {61                     temp_dis=ndis;62                     temp_x=nx;63                     temp_y=ny;64                 }65             }66             x[i]=temp_x;67             y[i]=temp_y;68             dis[i]=temp_dis;69         }70         delta*=0.8;71     }72 }73 int main()74 {75     scanf("%d",&T);76     while (T--)77     {78         scanf("%lf%lf%d",&boundary_x,&boundary_y,&cnt);79         for (int i=0;i<cnt;i++)80         scanf("%lf%lf",&hole_x[i],&hole_y[i]);81         sa();82         int tid;83         double temp_dis=0;84         for (int i=0;i<iP;i++)85         {86             if (dis[i]>temp_dis)87             {88                 tid=i;89                 temp_dis=dis[i];90             }91         }92         printf("The safest point is (%.1lf, %.1lf).\n",x[tid],y[tid]);93     }94     return 0;95 }