洛谷P1337 [JSOI2004]平衡点 / 吊打XXX

• 基本上是照着别人的代码写的，模拟退火为什么一定能找到答案呢。。。迷惑，，有时间搜一搜证明啥的

• sa步骤：这个是要确定一个(xi,yi)使得函数（）值最小，所以先选一个开始的点（这里选的是所有桌子上的点的均值），然后(rand()*2-RAND_MAX)*T就是deltax,deltay，然后再算出移动了这个delta后的函数值，该函数值如果是一个更小的值，则接受，否则如果（ exp(-delta/T)*RAND_MAX>rand() ）才接受，注意这里的delta是函数值的差值，这个exp(-delta/T)是一个在0，1之间的数。

• 产生移动距离：（rand()*2-RAND_MAX)*T  (这样正负都有）

• 以一定的概率接受移动：exp(-delta/T)*RAND_MAX>rand()

• 步骤：找到需要最优化的函数，找到移动方案，徐徐降温直到温度达到exp=1e-15退出，输出答案

• 代码：

  #include
  #define nmax 1010

  using namespace std;
  int n;
  double x[nmax],y[nmax],w[nmax];
  double ansx,ansy;
  const double eps=1e-;

  int cnt=;

  double f(double nx,double ny){
  double tot=,tmp;
  for (int i=; i<n; i++) {
  tmp=sqrt( (nx-x[i])*(nx-x[i])+(ny-y[i])*(ny-y[i]) );
  tot+=tmp*w[i];
  }
  return tot;
  }

  void sa(){
  double t=200.0;
  while(t>eps){
  double nowx=ansx+(rand()*-RAND_MAX)*t,nowy=ansy+(rand()*-RAND_MAX)*t;
  double delta=f(nowx,nowy)-f(ansx,ansy);
  if( delta< || ( exp(-delta/t)*RAND_MAX>rand() ) ) { ansx=nowx; ansy=nowy; }
  t*=0.998;
  }
  }

  int main(){
  srand((int)time(NULL));
  cin>>n;
  for (int i=; i<n; i++) {
  scanf("%lf%lf%lf",&x[i],&y[i],&w[i]);
  ansx+=x[i];
  ansy+=y[i];
  }
  ansx/=(double)n;
  ansy/=(double)n;
  sa();
  printf("%.3lf %.3lf\n",ansx,ansy);
  return ;
  }