【BZOJ1844/2210】Pku1379 Run Away
题意:矩形区域中有一堆点,求矩形中一个位置使得它到所有点的距离的最小值最大。
题解:模拟退火的裸题,再调调调调调参就行了~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn=1010;
struct pdd
{
double x,y;
pdd() {}
pdd(double a,double b) {x=a,y=b;}
}p[maxn];
int n;
double X,Y,T,mx;
pdd ans,now,neo;
double getdis(pdd a,pdd b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
double solve(pdd a)
{
double ret=1e10;
for(int i=1;i<=n;i++) ret=min(ret,getdis(a,p[i]));
if(ret>mx) mx=ret,ans=a;
return ret;
}
double Rand()
{
return rand()%1000/1000.0;
}
void work()
{
X=rd(),Y=rd(),n=rd();
int i,j;
for(i=1;i<=n;i++) p[i].x=rd(),p[i].y=rd();
mx=0;
for(j=1;j<=50;j++)
{
now.x=Rand()*X,now.y=Rand()*Y,solve(now),T=1000;
while(T>1e-3)
{
double a=2.0*acos(-1.0)*Rand();
neo.x=now.x+T*cos(a),neo.y=now.y+T*sin(a),T*=0.95;
if(neo.x<0||neo.x>X||neo.y<0||neo.y>Y) continue;
double de=solve(neo)-solve(now);
if(de>0) now=neo;
}
T=0.5;
for(i=1;i<=500;i++)
{
double a=2.0*acos(-1.0)*Rand();
neo.x=now.x+T*cos(a);
neo.y=now.y+T*sin(a);
if(neo.x<0||neo.x>X||neo.y<0||neo.y>Y) continue;
solve(neo);
}
}
printf("The safest point is (%.1lf, %.1lf).\n",ans.x,ans.y);
}
int main()
{
srand(2333666);
int T=rd();
while(T--) work();
}