传送门
正解是正交分解，然而我是当成模拟退火的入门题来写的
因为我脸黑，交了17次才过...
模拟退火过程：
初始温度定为一个较大的数
随机跳一段距离和方向，计算程度情况，如果比较稳定就选择它
不然就以一概率选择（跟温度和稳定程度差有关）
然后降低温度，重复上述过程
直到温度很低时退出
得到一组解，较大可能是最优解（看脸）
然后重复多次，一般就是最优解了（每次退火时选择当前最优解的位置会好一点）
怎样计算稳定程度也十分显然
哪里比较重平衡点肯定就往哪里跑
所以稳定程度与平衡点到物体的距离以及物体本身的重量有关
所以稳定程度 = 方向距离 * 重量（注意位置差有方向）
把所有物体的贡献加起来就行了
#include<iostream>#include<algorithm>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>inline int read(){ ???int x=0,f=1; char ch=getchar(); ???while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } ???while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } ???return x*f;}const int N=1e4+7;struct data{ ???int x,y,m;}d[N];int n;inline double get_energy(double &px,double &py)//计算稳定程度{ ???double res=0,xx,yy; ???for(int i=1;i<=n;i++) ???{ ???????xx=px-d[i].x; yy=py-d[i].y; ???????res+=sqrt(xx*xx+yy*yy)*d[i].m; ???} ???return res;}const double delta=0.993;double ansx,ansy;double ans=1e18+7,t;void SA(){ ???double xx=ansx,yy=ansy;//初始位置和稳定程度 ???t=3000;//初始温度 ???while(t>1e-15) ???{ ???????double nx=xx+(rand()*2-RAND_MAX)*t,ny=yy+(rand()*2-RAND_MAX)*t;//随机一个方向和距离 ???????//rand()*2-RAND_MAX是 -RAND_MAX到RAND_MAX的随机数 ???????double nans=get_energy(nx,ny);//计算稳定程度 ???????double DE=nans-ans; ???????if(DE<0)//如果更优就选择，并更新ans ???????{ ???????????xx=nx; yy=ny; ???????????ansx=nx; ansy=ny; ???????????ans=nans; ???????} ???????else if(exp(-DE/t)*RAND_MAX>rand())//不然以一个概率选择 ???????????xx=nx,yy=ny; ???????t*=delta; ???}}int main(){ ???n=read(); rand(); rand(); ???for(int i=1;i<=n;i++) d[i].x=read(),d[i].y=read(),d[i].m=read(); ???while((double)clock()/CLOCKS_PER_SEC<0.85) SA();//在不超时的情况下能跑几次退火就跑几次退火，然而这样也救不了来自非洲的我... ???printf("%.3lf %.3lf",ansx,ansy); ???return 0;}P1337 [JSOI2004]平衡点 / 吊打XXX
原文地址：https://www.cnblogs.com/LLTYYC/p/9813750.html