poj1379 模拟退火

【题意】

地图中有N个陷阱，给出他们的坐标，求一个点，使得这个点到所有陷阱的最小距离最大。

【题解】

乍一看是二分，但没有好方法。

看到题目要求的精度为0.1，则自然想到了模拟退火。

模拟退火的流程大致如下

1、随即生成若干解

2、定下步长d，和降温速度

3、开始模拟退火过程

【代码】

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cstring>
using namespace std;
const double pi=acos(-1.0);
const double INF=1e20;
const double eps=1e-3;

double px[31],py[31],d[31],x[1005],y[1005];

double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

int main()
{
    freopen("in.txt","r",stdin);
    int cc,X,Y,n,i,j,k;
    double theta,delta,tx,ty,td,dx,dy,ans,qx,qy;
    cin >> cc;
    srand((unsigned)time(NULL));
    while (cc--)
    {
        scanf("%d%d%d",&X,&Y,&n);
        for (i=1;i<=n;i++)
            scanf("%lf%lf",&x[i],&y[i]);
        for (i=1;i<=30;i++)
        {
            px[i]=double(rand()%1000+1)/1000.000*X;
            py[i]=double(rand()%1000+1)/1000.000*Y;
            d[i]=INF;
            for (j=1;j<=n;j++)
                d[i]=min(d[i],dist(px[i],py[i],x[j],y[j]));
        }
        delta=double(max(X,Y))/(sqrt(1.0*n));
        while (delta>eps)
        {
            for (i=1;i<=30;i++)
            {
                qx=px[i];qy=py[i];
                for (j=1;j<=30;j++)
                {
                    theta=double(rand()%1000+1)/1000.000*10*pi;
                    dx=delta*cos(theta);
                    dy=delta*sin(theta);
                    tx=qx+dx;ty=qy+dy;
                    if (tx<0 || tx>X || ty<0 || ty>Y)
                        continue;
                    td=INF;
                    for (k=1;k<=n;k++)
                        td=min(td,dist(tx,ty,x[k],y[k]));
                    if (td>d[i])
                    {
                        d[i]=td;px[i]=tx;py[i]=ty;
                    }
                }
            }
            delta*=0.8;
        }
        ans=0;
        for (i=1;i<=30;i++)
            if (d[i]>ans)
            {
                k=i;
                ans=d[i];
            }
        printf("The safest point is (%.1lf, %.1lf).\n",px[k],py[k]);
    }
    return 0;
}