题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

**[原题链接](https://www.luogu.org/problemnew/show/P1337)** **关于模拟退火的详细介绍，可以[peng-ym](https://www.cnblogs.com/peng-ym/p/9158909.html)关于模拟退火的介绍。** ## 题目描述 - 如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。 - 问绳结X最终平衡于何处。 - 注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。 ## 输入输出格式 - 输入格式： 文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 ) - 输出格式： 你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。 ## 解题思路 - 这题怕不是OI中为数不多的与物理有关系的题。~~（233）~~ - 题目询问的是绳结最终平衡于何处？ - 根据物理的知识，当系统处于平衡状态时，系统的总能量最小。 - 又此时系统的总能量是等于各个物体的重力势能，在质量一定时，即要求物体离地最近，离桌子最远。 - 那么，也就是绳子在桌子上的距离尽量的小。即：$\sum_{i=1}^{n}m_i*dist_{i,x}$最小。 - 模拟退火要解决的问题就是找到这一个点的位置。 - 模拟退火最主要的参数有几个：$T_0$初始温度，$t$每一次下降的温度，$ans$目前为止最优的答案，$now$新的状态，$delta$当前答案与最优答案的差值。 - 在扩展状态时有一个小方法：$(rand()*2-RANDMAX)*T$。这样的原理是$(rand()*2-RANDMAX)$的范围是从负数到正数的，这样子在扩展坐标的时候就可以多方向扩展，不会只在一个方向上更新。 - （PS：还有一个很重要的问题，玄学调参。这种问题最好在可以看到评测结果的OJ上交，不然你不会知道是自己打错了，还是参数没调好。。。。。。） ## 直接上代码： ```cpp #include<bits/stdc++.h> #define N 2000 using namespace std; template<typename T>inline void read(T &x) { x=0; static int p;p=1; static char c;c=getchar(); while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} x*=p; } struct node { double x,y,w; }e[N]; int n; double ansx,ansy; const double eps=1e-15; double f(double x,double y) { double tot=0; for(int i=1;i<=n;i++) { double delx=x-e[i].x; double dely=y-e[i].y; tot+=sqrt(delx*delx+dely*dely)*e[i].w; } return tot; } void mnth() { double T=200; while(T>eps) { double nowx=ansx+(rand()*2-RAND_MAX)*T; double nowy=ansy+(rand()*2-RAND_MAX)*T; double delta=f(nowx,nowy)-f(ansx,ansy); if(delta<0)ansx=nowx,ansy=nowy; else if(exp(-delta/T)*RAND_MAX>rand())ansx=nowx,ansy=nowy; T*=0.998; } } int main() { #ifndef ONLINE_JUDGE freopen("mnth.in","r",stdin); freopen("mnth.out","w",stdout); #endif srand((int)time(NULL)); read(n); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&e[i].x,&e[i].y,&e[i].w); ansx+=e[i].x;ansy+=e[i].y; } ansx/=(double)n;ansy/=(double)n; mnth(); printf("%.3lf %.3lf\n",ansx,ansy); return 0; } ```