HDU 1109

时间:2022-11-13 07:42:10

http://acm.hdu.edu.cn/showproblem.php?pid=1109

一个范围内给一堆点,求到这些点的最短距离最大

模拟退火,温度是步长

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <ctime>
#include <cmath>
using namespace std ;
const double eps=1e- ;
int X,Y,M ; struct point
{
double x,y ;
int OK()
{
if(x>-eps && x<X+eps && y>-eps && y<Y+eps)return ;
return ;
}
}p[],r[] ; double dis(point a,point b)
{
return sqrt(pow(a.x-b.x,)+pow(b.y-a.y,)) ;
} double ans[] ; int main()
{
int T ;
scanf("%d",&T) ;
srand(time(NULL)) ;
while(T--)
{
scanf("%d%d%d",&X,&Y,&M) ;
for(int i= ;i<M ;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y) ;
}
for(int i= ;i< ;i++)
{
r[i].x=(rand()%+)/1000.0*X ;
r[i].y=(rand()%+)/1000.0*Y ;
ans[i]=1e18 ;
for(int j= ;j<M ;j++)
{
ans[i]=min(ans[i],dis(p[j],r[i])) ;
}
}
double tmp=max(X,Y) ;
while(tmp>0.01)
{
for(int i= ;i< ;i++)
{
point now=r[i],next ;
for(int j= ;j< ;j++)
{
double rad=(rand()%+)/1000.0**3.1415926535 ;
next.x=now.x+cos(rad)*tmp ;
next.y=now.y+sin(rad)*tmp ;
if(!next.OK())continue ;
double m=1e18 ;
for(int k= ;k<M ;k++)
m=min(m,dis(p[k],next)) ;
if(m>ans[i])
{
ans[i]=m ;
r[i]=next ;
}
}
}
tmp*=0.8 ;
}
double res=0.0 ;
int idx ;
for(int i= ;i< ;i++)
{
if(ans[i]>res)
{
res=ans[i] ;
idx=i ;
}
}
printf("The safest point is (%.1lf, %.1lf).\n",r[idx].x,r[idx].y) ;
}
return ;
}