题目要求
最小（dis表示绳结到点i的距离），就是个广义费马点的题，模拟退火裸题QAQ
模拟退火就是优化后的爬山算法，一开始先随机一个平均点，接下来如果随机到的点比当前点劣，温度比较高的话也有几率跳过去，这样就能跳出一个局部最优解，随着温度降低，跳到劣点的概率越来越小
好喵喵的算法！
（这题好像黄学长直接爬山算法也过了，模拟退火贼慢T^T
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #define ll long long using namespace std; const int maxn=500010,inf=1e9; int n; double ans,ansx,ansy; double x[maxn],y[maxn],g[maxn]; double dis(double x1,double y1,double x2,double y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} double cal(double xx,double yy) { double sum=0; for(int i=1;i<=n;i++)sum+=g[i]*dis(xx,yy,x[i],y[i]); if(sum<ans)ans=sum,ansx=xx,ansy=yy; return sum; } double Rand(){return rand()%1000/1000.0;} void sa(double T) { double nowx=ansx,nowy=ansy; while(T>1e-3) { double nextx=nowx+T*(Rand()*2-1); double nexty=nowy+T*(Rand()*2-1); double dE=cal(nowx,nowy)-cal(nextx,nexty); if(dE>0||exp(dE/T)>Rand())nowx=nextx,nowy=nexty; T*=0.991; } for (int i=1;i<=1000;i++) { double nextx=ansx+T*(Rand()*2-1); double nexty=ansy+T*(Rand()*2-1); cal(nextx,nexty); } } int main() { srand(2333333); scanf("%d",&n);ans=2333333333333333333ll; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&x[i],&y[i],&g[i]); ansx+=x[i];ansy+=y[i]; } ansx/=n;ansy/=n;sa(100000); printf("%.3lf %.3lf",ansx,ansy); return 0; }