题意:给出n条无限长绳子,绳子一端绑着重物,另一端汇集到一起成为一个点,初始重物均位于桌面上,每个重物有一个坐标(x,y),让后让重物自由落体,问整个系统平衡时绳子汇点位于何处?
分析:一道模拟退火的题目,我们首先对n个点求一下平均值,确定一下结果的大概位置。然后O(n)遍历这n个点,将这n个点的拉力全部正交分解到x轴,y轴上,求x轴合力mgx,求y轴合力mgy。若mgx<0,将该点向正向移动,否则负向移动;对mgy的操作同理。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5000; const double eps=1e-14; const double ep=0.0000005; int n; struct Node{ double xi; double yi; double wi; }p[maxn]; double xishu=0.00993; double dis(double x,double y,double x0,double y0){ return sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0)); } double fenjie(double a,double b){ return a-b; } void SA(double x,double y,double w){ double T=10000; while(T>eps){ double temx=0,temy=0; for(int i=1;i<=n;i++){ double L=dis(x,y,p[i].xi,p[i].yi); if(L==0)continue; //如果L==0,不能做分母,所以要continue temx+=p[i].wi/L*fenjie(x,p[i].xi);//计算x轴上合力 temy+=p[i].wi/L*fenjie(y,p[i].yi);//计算y轴上合力 } if(abs(temx-0)<ep&&abs(temy-0)<ep)break;//优化 if(temx<0) //如果合力向在x轴负向,点就向x轴正向移动 x+=(0-temx)*xishu; else x-=(temx-0)*xishu; if(temy<0) //如果合力向在y轴负向,点就向y轴正向移动 y+=(0-temy)*xishu; else y-=(temy-0)*xishu; T*=0.987; xishu*=0.9999; } printf("%.3f %.3f\n",x,y); } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>p[i].xi>>p[i].yi>>p[i].wi; double avex=0; double avey=0; double avew=0; for(int i=1;i<=n;i++){ avex+=p[i].xi; avey+=p[i].yi; } avex/=n; avey/=n; for(int i=1;i<=n;i++) avew+=p[i].wi*dis(p[i].xi,p[i].yi,avex,avey); SA(avex,avey,avew); return 0; }