这个算法名字听起来好可怕，，，但是代码却很容易实现
传说中的模拟退火，，从物理学角度上讲，加热后分子会均匀扩散，而且温度越高扩散的距离越大，然后降温后，，扩散的距离也会慢慢的减小，，随后整个状态平衡。
噗，算了，还是从程序的角度思考把。。
刚开始的时候，在(0,0)到(X,Y)这个矩阵中随机取30个点，当作是起始的源点。然后设置步长（开始可能会比较大）
然后就可以开始扩散节点了了
遍历30个点，随机取周围的一个方向，然后点向这个方向偏移步长的大小，然后判断这个点是否合法，再判断这个点的答案是否更优（也就是离最近的地雷的距离是否比刚开始更大），如果更优，就更新以前的点，一直循环30次
所以这30个点现在答案都更优了，然后开始模拟退火，让步长减小
然后再循环上面的操作，直到步长小于一个精度，这题就做完了
我的理解是，，如果把整个答案理解成一个三维的模型，z表示(x,y)这个点距最近的地雷的距离，那么整个模型就能看作是有许多山峰组成的三维模型了
我们要找的，就是最高的山峰
模拟退火就是找了30个人，随机分布在这个地图里，然后让他们在自己的位置，向四周看，刚开始的目光看的很远，发现那个地方的高度更高，那么就走到那里去
然后目光慢慢的减短，移动的距离也稍微变短，这样人就会一直向着最高峰靠近。
整个地图中，可能会有许多个高峰，难免会出现局部答案，也就是不是极值，但是因为有30个人，所以总会有很大的概率有人是来到了最高峰
所以最后再在这30个人中找到最高的，那么就是最高峰了
感觉随机算法太强大了，，本来应该要用二分的感觉，，竟然可以利用随机这样来做，也是跪了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1500 + 5;
const int INF = 0x3f3f3f3f;
const double exps = 1e-3;//比要求精度低2个就行
const double pi = acos(-1.0);double fx[MX], fy[MX], best[MX];
double PX[MX], PY[MX];double Rand(double L, double R) {//区间内随机数生成函数return (rand() % 10000) / 10000.0 * (R - L) + L;
}double dist(double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}int main() {int T, X, Y, n;scanf("%d", &T);srand(time(NULL));while(T--) {scanf("%d%d%d", &X, &Y, &n);for(int i = 1; i <= n; i++) {scanf("%lf%lf", &PX[i], &PY[i]);}for(int i = 1; i <= 30; i++) {fx[i] = Rand(1, X);fy[i] = Rand(1, Y);best[i] = INF;for(int j = 1; j <= n; j++) {best[i] = min(best[i], dist(fx[i], fy[i], PX[j], PY[j]));//评估函数，靠它来评估整个退火过程的好坏}}double step = max(X, Y);//一般是最长的跨度while(step > exps) {for(int i = 1; i <= 30; i++) {//初始状态一般30个for(int j = 1; j <= 30; j++) {//一般循环30次即可double angel = Rand(0, 2 * pi);//枚举任何角度，使得到的新点向四周扩散double nx = fx[i] + cos(angel) * step;double ny = fy[i] + sin(angel) * step;if(nx < 0 || nx > X || ny < 0 || ny > Y) continue;double d = INF;for(int k = 1; k <= n; k++) {d = min(d, dist(nx, ny, PX[k], PY[k]));}if(d > best[i]) {best[i] = d;fx[i] = nx;fy[i] = ny;}}}step *= 0.85;//退火，常数，不管}int t = 1;for(int i = 1; i <= 30; i++) {if(best[i] >= best[t]) {//找到退火后的状态中，最优的t = i;}}printf("The safest point is (%.1lf, %.1lf).\n", fx[t], fy[t]);}return 0;
}