(贪心：模拟退火算法)洛谷P1337 [JSOI2004]平衡点 / 吊打XXX

链接：https://www.luogu.com.cn/problem/P1337
模拟退火算法学习参考：
https://www.cnblogs.com/flashhu/p/8884132.html
https://99nl.blog.luogu.org/guan-yu-mu-ni-tui-huo-di-xue-xi-bi-ji
思路：
模拟退火适用的问题通常是一些求最优解的问题
比如把问题抽象地看成一个长得毫无规律的函数，而最优解就是函数的最低点。

模拟退火过程简要概述：
我们给一个初始解x，并让它不断变动。要模拟变动的大小随温度的降低而降低，我们每次的delta x应该在一个大小与T成正比的范围内随机取值。
这时候我们就要考虑是否将当前解变为目标解，因为我们还是要贪心，如果当前f(x1) < f(x)，那么就接受目标解，x=x1，
那如果f(x1)>f(x)呢？我们要以一定概率来接受它，这样才能跳出局部的限制，去搜寻更优的解，弥补贪心的局限性。，科学家通过分析，得出结论，这个概率是
如此反复一直到T趋近于0(可以设一个eps)，这时候我们认为当前的解x就是最优解。

我们回过来看这道题
达到稳定状态的时候，系统的总能量最小。而总的能量来源于每个物体的重力势能之和。要想让每个物体的重力势能减小，那就让拉着它的绳子在桌面下面的长度尽可能地长，也就是桌面上尽可能地短。由此看来，某个物体的势能与桌面上绳子的长度、物体重量都成正比。
于是，为了找到平衡点，我们要找一个点使得 最小(di为绳结到i点的距离)
函数已经求出来了，接下来就是正常模拟退火的过程。
首先初始解可以设为(x1+x2+x3+...+xn)/n, (y1+y2+y3+...+yn)/n，更接近正解。解变动值可以随机两个值 和
RAND_MAX常数是rand的最大值
rand()是生成一个0到RAND_MAX的随机值，两者搭配起来用来求0到1.0的随机值还是很方便的。
代码：

#include<bits/stdc++.h>
#define down 0.996
#define eps 1e-15
#define RD (rand()*2-RAND_MAX)    //用于生成-RAND_MAX到RAND_MAX的任意数
using namespace std;

struct node{
    int x, y, w;
}a[2005];    //存下物体的坐标 

int n;
double ansx, ansy, answ;    //最终答案 

double energy(double x, double y)    //跟据物理学知识，能量总合越小越稳定 
{
    double r = 0, dx, dy;
    for(int i = 1; i <= n; i++)
    {
        dx = x-a[i].x;
        dy = y-a[i].y;
        r += sqrt(dx*dx+dy*dy)*a[i].w; 
    }
    return r;
}

void sa()    //模拟退火 
{
    double t = 3000;    //温度要足够高 
    while(t > eps)    //略大于0 
    {
        double ex = ansx+RD*t;    //随机产生新答案 
        double ey = ansy+RD*t;
        double ew = energy(ex, ey);
        double de = ew-answ;
        if(de < 0)//如果此答案更优，就接受 
        {
            ansx = ex;
            ansy = ey;
            answ = ew;
        }
        else if(exp(-de/t)>rand()/RAND_MAX)    //否则按照概率接受 
        {
            ansx = ex;
            ansy = ey;
        }
        t *= down;
    }
}

void solve()//多跑几遍退火，增加得到最优解的概率 
{
    sa();
    sa();
    sa();
    sa();
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
        ansx+=a[i].x;
        ansy+=a[i].y;
    }
    ansx/=n;    //以平均数作为初始答案 
    ansy/=n;
    answ=energy(ansx, ansy);
    solve();
    printf("%.3f %.3f\n",ansx,ansy);

    return 0; 
}