luogu1337 [JSOI2004]平衡点 / 吊打XXX(模拟退火）

推荐博客：模拟退火总结（模拟退火）by FlashHu。模拟退火的原理，差不多就是不断地由现有的值不断地试探，不断地转到更优的值，并在一定概率下转到较差的值。

题目传送门：luogu1337 [JSOI2004]平衡点 / 吊打XXX

题目转述：平面上有n个点，每个点有自己的位置(xi),(yi)和权值(wi)。求一个新点的位置(x),(y)，使得该点到其余所有点距离与权值之积的和最小。也即(sumlimits_{i=1}^n sqrt((x-x[i])^2+(y-y[i])^2)*w[i])最小。也即原题中各方块的重力势能最小。

题目分析：对(x),(y)进行模拟退火。题目中用了(long double)，因为(double)总是会锅。另外注意(RAND_MAX)的用法。

AC代码：

#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
typedef long long ll;
const int maxn = 1000;
const long double D = 0.98;
const long double eps = 1e-14;

using namespace std;

long double x[maxn+10],y[maxn+10],w[maxn+10];

int n;

long double calc(long double xx,long double yy)
{
    long double res=0,dx,dy;
    for(int i=1; i<=n; i++)
    {
        dx = x[i]-xx,dy = y[i]-yy;
        res += sqrt(dx*dx+dy*dy)*w[i];
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    long double bx=0,by=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%Lf%Lf%Lf",x+i,y+i,w+i);
        bx += x[i]; by += y[i];
    }
    bx /= n; by /= n;

    long double best = calc(bx,by);
    srand(time(NULL));
    int times = 1;
    while(times--)
    {
        long double ans = best;
        long double x0 = bx,y0 = by;
        for(long double T=50000; T>eps; T*=D)
        {
            long double x1 = x0 + T*(rand()*2-RAND_MAX);
            long double y1 = y0 + T*(rand()*2-RAND_MAX);
            long double res = calc(x1,y1);
            if(best>res)
                best=res,bx=x1,by=y1;
            if(ans>res||exp((ans-res)/T)>(long double)rand()/RAND_MAX)
                ans=res,x0=x1,y0=y1;
        }
    }
    printf("%.3Lf %.3Lfn",bx,by);
    return 0;
}