[POJ 1379] [CEOI 1999] 逃离陷阱

模拟退火。

概念见大白话解析模拟退火算法

实现:

首先随机在平面中取一个点 A,每轮都以这个点为圆心,R 为半径(每轮递减)随机选取若干个圆上的点 B。若点 B 已经优于 A,则直接用 B 更新 A,否则以一个概率 P(每轮递减)决定是否以 B 更新 A。这样就可以得到一个近似最优解。

在实现过程中,可以同时维护 20 个点,最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<ctime>

using namespace std;

inline void set_file_IO(string);
inline void close_IO(void);
inline void work(void);

int main(void) {
    #ifndef ONLINE_JUDGE
        set_file_IO("away");
    #endif
    ios::sync_with_stdio(false);
    work();
    #ifndef ONLINE_JUDGE
        close_IO();
    #endif
    return 0;
}

const double Pi = acos(-1.);

int w, h, m;

inline int random(const int l, const int r) {
    return l + (rand() % (r-l+1));
}

inline double random_real(void) {
    return ((((rand() << 15) | rand()) & 0x3FFFFFFF) + 0.) / (0x3FFFFFFF + 0.);
}

inline double sqr(const double x) {
    return x * x;
}

struct point {
    double x, y, d;
    
    void calc(void);
    
    point() {}
    point(const double _x, const double _y) {
        x = _x;
        y = _y;
        this->calc();
    }
    
    void jump(const double r, const double T) {
        const double theta = random(0, 359) / 180. * Pi;
        point b = point(x + r * cos(theta), y + r * sin(theta));
        if (b.x<0 || b.y<0 || b.x>w || b.y>h) {
            return ;
        }
        if (b.d > d || random_real() <= exp(-(d - b.d) / T)) {
            *this = b;
        }
    }
} hole[1100], p[23];

void point::calc(void) {
    d = 1e10;
    for (int i=1; i<=m; ++i) {
        d = min(d, sqrt(sqr(this->x - hole[i].x) + sqr(this->y - hole[i].y)));
    }
}

inline void PA(void) {
    const int n = 20;
    
    for (int i=1; i<=n; ++i) {
        p[i] = point(random(0, w), random(0, h));
    }
    
    for (double T = 1000, delta = max(w, h) / sqrt(n+0.); delta > 1e-7; delta *= 0.9, T *= 0.8) {
        for (int i=1; i<=n; ++i) {
            for (int j=0; j<30; ++j) {
                p[i].jump(delta, T);
            }
        }
    }
    
    int pos = 1;
    for (int i=2; i<=n; ++i) {
        if (p[i].d > p[pos].d) {
            pos = i;
        }
    }
    cout << "The safest point is (" << p[pos].x << ", " << p[pos].y << ")." << endl;
}

inline void single_case(void) {
    cin >> w >> h >> m;
    for (int i=1; i<=m; ++i) {
        cin >> hole[i].x >> hole[i].y;
    }
    PA();
}

inline void work(void) {
    srand(time(0));
    cout << setiosflags(ios::fixed) << setprecision(1);
    int cases;
    cin >> cases;
    while (cases --) {
        single_case();
    }
}

inline void set_file_IO(string name) {
    freopen((name + ".in" ).c_str(), "r", stdin );
    freopen((name + ".out").c_str(), "w", stdout);
}

inline void close_IO(void) {
    fclose(stdin);
    fclose(stdout);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注