题意:和上题一样。。。就是把最小值换成了最大值。。
ref:http://www.cppblog.com/RyanWang/archive/2010/01/21/106112.html
#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个方向发散
#define INF 99999.999
int X,Y,N,T;
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=INF;
for(int i=;i<=N;i++)
{
double tx=hol[i].x,ty=hol[i].y;
tmp=min(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));
cin>>T;
//cout<<T<<endl;
while(T--)
{
cin>>X>>Y>>N;
for(int i=;i<=N;i++)
cin>>hol[i].x>>hol[i].y; sa(); ans=0.000;
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("The safest point is (%.1f, %.1f).\n",tp[ansi].x,tp[ansi].y);
//printf("%.1lf\n",ans);
}
return ;
}