第一道模拟退火题$qwq$

什么！我这个万年蒟蒻居然学会了模拟退火！是不是明天就要火星撞地球了！qwq

然而玄学调参成功卡了我九次……也许是我太非了？

------------

正解：

我们可以确定一个原点，将所有的力在这个原点上正交分解，最终我们可以得到所有的力的一个合力，而真正的平衡点一定在合力所指向的方向每当分得到一个合力之后，将原点在合力的方向上位移一定的距离。每当原点位移的方向发生了改变的时候，缩小以后操作的位移距离。 例如：上次操作是将原点像 x 轴正方向移动，而当前移动是将原点像 x 轴负方向上移动，这说明原点的横坐标一定在这两次假设的原点的横坐标中间， 因此我们缩小以后原点移动的距离。当两次移动的坐标差在一定的范围之内时，说明我们得到了解，输出即可。——摘自题解

完全看不懂，于是模拟退火qwq

由常识可知，题中描述的一个系统在平衡情况下的总能量最小。

又此时系统的总能量是等于各个物体的重力势能，在质量一定时，即要求物体离地最近，离桌子最远。

即使得$\sum_{i=1}^ndis_i*w_i$最小。

剩下的就是模板。

1 #include 
     
       2 #define INF 1e18 3 using namespace std; 4 double energy = INF, ansx, ansy, n; 5 const double delta = 0.996;//降温系数 6 struct node { 7     int x, y, w; 8 }a[1010]; 9 10 inline int read() {
   //快读11     int res = 0, flag = 1;12     char c = getchar();13     for(; !isdigit(c); c = getchar()) if(c == '-') flag = -1;14     for(; isdigit(c); c = getchar()) res = (res<<3) + (res<<1) + (c^48);15     return res * flag;16 }17 18 inline double calc_dis(double x1, double y1, double x2, double y2) {
   //计算平面上两点之间距离19     return sqrt(fabs(x1-x2) * fabs(x1-x2) + fabs(y1-y2) * fabs(y1-y2));20 }21 22 inline double calc_energy(double x,double y) {
   //计算当前系统的势能23     double res = 0;24     for(register int i = 1; i <= n; i++) res += calc_dis(x, y, a[i].x, a[i].y) * a[i].w;25     return res;26 }27 28 inline void metaphysics() {
   //玄学qwq29     double x = ansx, y = ansy, t = 2800;//将初始值赋为上次最优解，便于快速逼近最优解30     while(t > 1e-13) {
   //终止温度31         double nx = x + ((rand()<<1) - RAND_MAX) * t;32         double ny = y + ((rand()<<1) - RAND_MAX) * t;//产生-RAND_MAX~RAND_MAX之间的随机坐标，变化幅度为当前温度t33         double nenergy = calc_energy(nx, ny);34         double Delta = nenergy - energy;//当前解与最优解之间的差值35         if(Delta < 0) x = nx, y = ny, ansx = x, ansy = y, energy = nenergy;//更优，直接转移36         else if(exp(-Delta/t) * RAND_MAX > rand()) x = nx, y = ny;//否则以一定概率接受该转移37         t *= delta;//降温38     }39 }40 41 int main() {42     int sumx = 0, sumy = 0;43     srand(time(NULL)), srand(rand()), srand(rand());//玄学srand()qwq44     n = read();45     for(register int i = 1; i <= n; i++)46         a[i].x = read(), a[i].y = read(), a[i].w = read(), sumx += a[i].x, sumy += a[i].y;47     ansx = (double)sumx/n, ansy = (double)sumy/n;//从平均值开始，更容易逼近最优解48     metaphysics();49     metaphysics();50     metaphysics();51     metaphysics();52     metaphysics();//模拟退火五次，增大找到最优解概率53     printf("%.3lf %.3lf\n", ansx, ansy);54     return 0;55 }