模拟退火绝对是从OI--ACM以来接触过的所有算法里面最黑科技的orz
题意:地上有一堆hole,要找一个点,使得(距离该点最远的hole的距离)最小。
sol:本来想套昨天的模拟退火模板,初值(0,0),向8个方向扩散。
然而这题并没有这么naive。
模板2.0 get:
#define eps 1e-3
#define pi acos(-1.0)
#define POI 15 //独立跑POI次,找其中最小的 tp[1..POI]是随机的初值
#define RUN 40 //迭代次数,本题中即点(tx,ty)向RUN个方向发散 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;
}
}
AC Code:
#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个方向发散
int X,Y,N;
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=0.000;
for(int i=;i<=N;i++)
{
double tx=hol[i].x,ty=hol[i].y;
tmp=max(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));
while(cin>>X>>Y>>N)
{
for(int i=;i<=N;i++)
cin>>hol[i].x>>hol[i].y; sa(); ans=(X*X+Y*Y)*100.0;
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("(%.1f,%.1f).\n",tp[ansi].x,tp[ansi].y);
printf("%.1lf\n",ans);
}
return ;
}
ref:
http://blog.csdn.net/acm_cxlove/article/details/7954321
http://blog.csdn.net/zxy_snow/article/details/6682926
http://www.kuangbin.net/archives/hdu3932#more-435