模拟退火。
概念见大白话解析模拟退火算法。
实现：
首先随机在平面中取一个点 A，每轮都以这个点为圆心，R 为半径（每轮递减）随机选取若干个圆上的点 B。若点 B 已经优于 A，则直接用 B 更新 A，否则以一个概率 P（每轮递减）决定是否以 B 更新 A。这样就可以得到一个近似最优解。
在实现过程中，可以同时维护 20 个点，最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。
代码如下：
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<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);
}