题目链接

题意:给出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;
}