P1337 平衡点/吊打XXX 模拟退火（话说吊打的XXX到底是谁）

· · 题解

最近练模拟退火ing，参考Flash_Hu大犇的博客后根据自己理解，对《平衡点/吊打XXX》这个题整理出了一份题解。至于讲解嘛，就用胡犇的博客吧，写不到那么好呀（主要是懒？），我就简单提一下。

当时见到这个题的题干，真是帅脸懵B，在想算法之前就死在了读题上（你体会过绝望吗）。后来得高人指点，他告诉我这是一道物理逻辑题，最终我得到如下思路：

坐标稳定 ——> 能量稳定 ——> 势能总和最小 ——> E=mgh ——>( 重物高度 x 对应M)最低 ——> (桌下的绳子长度 x 对应M)最大 ——> (桌面上的绳长 x 对应M)最小

讲解戳这里 ：http://www.cnblogs.com/flashhu/p/8884132.html

代码看下面：

#include<bits/stdc++.h>
using namespace std;

#define RD T*(rand()*2-RAND_MAX)
//生成[-T*RAND_MAX,T*RAND_MAX)的随机变动范围（rand():[0,RAND_MAX)）
#define ld long double
#define il inline

const ld D = 0.99, EPS = 1e-15;//D:温度变化率
const int N = 1005;
ld best, ans, bx, by, res;//bx:best_x, by:best_y
double x[N], y[N], w[N];
int n;

il ld calc(ld x0, ld y0)  {//求总势能 
  ld dx, dy, res = 0;
  for(int i = 1; i <= n; ++i)  {
    dx = x[i]-x0;  dy = y[i]-y0;
    res += sqrt(dx*dx+dy*dy)*w[i];//三角函数都会吧
  }
  return res;
}

int main()  {
  ld x0, y0, x1, y1;//注意：这几个函数名不能用作全局变量

  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)  {
    scanf("%lf%lf%lf", x+i, y+i, w+i);
    bx+=x[i], by+=y[i];
  }
  best = ans = calc(bx/=n,by/=n);//初始横纵坐标均选择平均值

  srand(20020202);//这里最好不要用time(NULL)，否则可能同组输入数据得到不同答案，被评测机WA掉。

/*******祝她17岁生日快乐*******/

  int tim = 1;
//一般模拟退火只要温度和降温率对一次就够了（非酋除外）
  while(tim--)  {
    ans = best;
    x0 = bx, y0 = by;
    for(ld T=1000000; T>EPS; T*=D)  {
      x1 = x0+RD, y1 = y0+RD;
      res = calc(x1,y1);
      if(best > res)//更新最优答案
        best = ans, bx = x1, by = y1;
      if(ans>res || exp((ans-res)/T) > (ld)rand()/RAND_MAX)//exp:返回e的 n次幂(e^n)
        ans = res, x0 = x1, y0 = y1;//接受新解
    }
  }

  printf("%.3Lf %.3Lf", bx, by);//注意空格哈

  return 0;
}
//祝各位OIer们新年快乐！