[POJ 1379] | Eurce's Blog

模拟退火

题意：在最大10000*10000平面的上有最多1000个洞，求平面上的某个点，使得其离所有洞的最近距离最大化。输出精度为小数点后1位。

分析：按照模拟退火的思想，在平面上随机取10个点，将单次移动的步长设为算法中的温度，移动方向随机。初始温度设为矩形对角线长的一半，每轮迭代后温度降为之前的0.8。每轮迭代时，对于每个点，按照当前步长尝试移动50次，如果目标点更优则更新位置，否则维持原位。当温度降低到0.001以下时，终止算法，并取10个点中的最优值输出。

#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-3
#define its 50
#define pl 10
#define pi 3.141592653589793

int n;
double r,c,x[1000],y[1000];
double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)
{
    int i;
    double d=1e30;
    for(i=0;i<n;i++)
        d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));
    return d;
}

bool chk(double xu,double yu)
{
    return xu>0&&xu<r&&yu>0&&yu<c;
}

void init()
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<pl;i++)
    {
        xp[i]=r*0.001*(rand()%1000);
        yp[i]=c*0.001*(rand()%1000);
        dp[i]=calc(xp[i],yp[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double a,g,xv,yv,vd,xu,yu,ud;
    srand(time(0));
    for(l=0;l<pl;l++)
    {
        xv=xp[l];
        yv=yp[l];
        vd=dp[l];
        for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)
        {
            for(i=0;i<its;i++)
            {
                a=2*pi*0.001*(rand()%1000);
                xu=xv+g*cos(a);
                yu=yv+g*sin(a);
                if(!chk(xu,yu))
                    continue;
                ud=calc(xu,yu);
                if(ud>vd)
                {
                    xv=xu;
                    yv=yu;
                    vd=ud;
                }
            }
        }
        xp[l]=xv;
        yp[l]=yv;
        dp[l]=vd;
    }
    for(l=0,ud=0;l<pl;l++)
    {
        if(dp[l]>ud)
        {
            ud=dp[l];
            xv=xp[l];
            yv=yp[l];
        }
    }
    printf("The safest point is (%.1f, %.1f).\n",xv,yv);
}

int main()
{
    scanf("%*d");
    while(~scanf("%lf%lf%d",&r,&c,&n))
    {
        init();
        solve();
    }
    return 0;
}

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-3

#define its 50

#define pl 10

#define pi 3.141592653589793

int n;

double r,c,x[1000],y[1000];

double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)

{

int i;

double d=1e30;

for(i=0;i<n;i++)

d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));

return d;

}

bool chk(double xu,double yu)

{

return xu>0&&xu<r&&yu>0&&yu<c;

}

void init()

{

int i;

for(i=0;i<n;i++)

scanf("%lf%lf",x+i,y+i);

for(i=0;i<pl;i++)

{

xp[i]=r*0.001*(rand()%1000);

yp[i]=c*0.001*(rand()%1000);

dp[i]=calc(xp[i],yp[i]);

}

void solve()

{

int i,j,k,l;

double a,g,xv,yv,vd,xu,yu,ud;

srand(time(0));

for(l=0;l<pl;l++)

{

xv=xp[l];

yv=yp[l];

vd=dp[l];

for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)

{

for(i=0;i<its;i++)

{

a=2*pi*0.001*(rand()%1000);

xu=xv+g*cos(a);

yu=yv+g*sin(a);

if(!chk(xu,yu))

continue;

ud=calc(xu,yu);

if(ud>vd)

{

xv=xu;

yv=yu;

vd=ud;

}

xp[l]=xv;

yp[l]=yv;

dp[l]=vd;

}

for(l=0,ud=0;l<pl;l++)

{

if(dp[l]>ud)

{

ud=dp[l];

xv=xp[l];

yv=yp[l];

}

printf("The safest point is (%.1f, %.1f).\n",xv,yv);

}

int main()

{

scanf("%*d");

while(~scanf("%lf%lf%d",&r,&c,&n))

{

init();

solve();

}

return 0;

}

ps：非常山寨的实现方式，没有考虑目标位置并非更优时仍进行移动的方案。本题的数据也是很松，只要控制好初始点数，温度下降幅度以及迭代次数，时限范围内很易求得最优位置。