首页 > ACM题库 > HDU-杭电 > HDU 1109 Run Away-模拟退火-[解题报告] C++
2013
11-27

HDU 1109 Run Away-模拟退火-[解题报告] C++

Run Away

问题描述 :

One of the traps we will encounter in the Pyramid is located in the Large Room. A lot of small holes are drilled into the floor. They look completely harmless at the first sight. But when activated, they start to throw out very hot java, uh … pardon, lava. Unfortunately, all known paths to the Center Room (where the Sarcophagus is) contain a trigger that activates the trap. The ACM were not able to avoid that. But they have carefully monitored the positions of all the holes. So it is important to find the place in the Large Room that has the maximal distance from all the holes. This place is the safest in the entire room and the archaeologist has to hide there.

输入:

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing three integers X, Y, M separated by space. The numbers satisfy conditions: 1 <= X,Y <=10000, 1 <= M <= 1000. The numbers X and Yindicate the dimensions of the Large Room which has a rectangular shape. The number M stands for the number of holes. Then exactly M lines follow, each containing two integer numbers Ui and Vi (0 <= Ui <= X, 0 <= Vi <= Y) indicating the coordinates of one hole. There may be several holes at the same position.

输出:

Print exactly one line for each test case. The line should contain the sentence “The safest point is (P, Q).” where P and Qare the coordinates of the point in the room that has the maximum distance from the nearest hole, rounded to the nearest number with exactly one digit after the decimal point (0.05 rounds up to 0.1).

样例输入:

3
1000 50 1
10 10
100 100 4
10 10
10 90
90 10
90 90
3000 3000 4
1200 85
63 2500
2700 2650 
2990 100

样例输出:

The safest point is (1000.0, 50.0).
The safest point is (50.0, 50.0).
The safest point is (1433.0, 1669.8).

我的第一篇模拟退火,先是看资料,发现太高深,又去搜博客什么的,在一个地方看到了比较通俗的解读。至今还只是会写,不懂得原理是什么,能ac也是碰巧,发现太高深而且又属于YY型的算法,果断过一题放弃掉。下面贴上代码:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <limits.h>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <cmath>
#include <queue>

#define P 0.6
#define INF 0x7fffffff

using namespace std;

const int N=1001;
const int maxn=10;
const int maxd=25;

struct node
{
    double x;
    double y;
    double dis;
}p[N],tr[maxn];

int x,y,n;

inline int max(int x,int y)
{
    return x<y?y:x;
}

double get_dis(node t)
{
    double mi=INT_MAX;
    for(int i=0;i<n;i++)
    {
        double dis=(t.x-p[i].x)*(t.x-p[i].x)+(t.y-p[i].y)*(t.y-p[i].y);
        if(dis<mi)
            mi=dis;
    }
    return mi;
}

node get_ans()
{
    node tmp;
    double t,t_min=(1e-2)*5,k1,k2;
    t=max(x,y)*1.0/sqrt(n*1.0);
    for(int i=0;i<maxn;i++)
    {
        tr[i].x=((rand()%1000+1)*1.0/1000.00)*x;
        tr[i].y=((rand()%1000+1)*1.0/1000.00)*y;
        tr[i].dis=get_dis(tr[i]);
    }
    while(t>t_min)
    {
        for(int i=0;i<maxn;i++)
        {
            for(int j=1;j<=maxd;j++)
            {
                k1=(double)(rand()%1000+1)*1.0/1000.00*t;
                k2=sqrt(t*t-k1*k1);
                if(rand()%2) k1*=-1;
                if(rand()%2) k2*=-1;
                tmp.x=tr[i].x+k1;
                tmp.y=tr[i].y+k2;
                if(tmp.x>=0&&tmp.x<=x&&tmp.y>=0&&tmp.y<=y)
                {
                    tmp.dis=get_dis(tmp);
                    if(tmp.dis>tr[i].dis)
                        tr[i]=tmp;
                }
            }
        }
        t=t*P;
    }
    int max=0;
    for(int i=1;i<maxn;i++)
    {
        if(tr[i].dis>tr[max].dis)
            max=i;
    }
    return tr[max];
}

int main()
{
    int t;
    node ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&x,&y,&n);
        for(int i=0;i<n;i++)
            scanf("%lf %lf",&p[i].x,&p[i].y);
        ans=get_ans();
        printf("The safest point is (%.1lf, %.1lf).\n",ans.x,ans.y);
    }
    return 0;
}

也不想解释什么了,也是基本照搬别人东西,也觉得自己比较猥琐。不会呀,伤不起。。


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环