P1337 [JSOI2004]平衡点 / 吊打XXX

题面

如图：有 \(n\) 个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中 \(X\) 处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结X最终平衡于何处。

注意：桌面上的洞都比绳结 \(X\) 小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

分析

这是一道题目二分题目，但模拟退火也能过。

编写降温函数

double f(double nowx,double nowy){
    double sum=0;
    for(int i=1;i<=n;i++){
        double delx=nowx-node[i].x;
        double dely=nowy-node[i].y;
        sum+=(sqrt(delx*delx+dely*dely))*node[i].weight;
    }
    return sum;
}

组装

#include 
#define namesapce namespace
using namesapce std;
struct Thing{
    int x,y,weight;
}node[10005];
int n;

double f(double nowx,double nowy){
    double sum=0;
    for(int i=1;i<=n;i++){
        double delx=nowx-node[i].x;
        double dely=nowy-node[i].y;
        sum+=(sqrt(delx*delx+dely*dely))*node[i].weight;
    }
    return sum;
}
const double eps=1e-14;
double xans,yans;
double ans=1e18;
void simulate_anneal(double delta,double t){
    double xx=xans;
    double yy=yans;
    while(t>eps){
        double xtemp=xans+(rand()*2-RAND_MAX)*t;
        double ytemp=yans+(rand()*2-RAND_MAX)*t;
        double new_ans=f(xtemp,ytemp);
        double DE=new_ans-ans;
        if(DE<0){
            xx=xtemp;
            yy=ytemp;
            xans=xx;
            yans=yy;
            ans=new_ans;
        }
        else if(exp(-DE/t)*RAND_MAX>rand()){
            xx=xtemp;
            yy=ytemp;
        }
        t*=delta;
    }
}
int main(){
	 srand(time(0));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>node[i].x;
        cin>>node[i].y;
        cin>>node[i].weight;
    }
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    simulate_anneal(0.993,1926);
    printf("%.3lf %.3lf",xans,yans);
    return 0;
}

没想到吧！算法界竟然还有srand和rand!

提交

提交前建议洗脸并拜佛，获得神灵保佑。

提交了\(seven\)遍才过，看来脸还不够干净。（大家也来测试自己的脸部干净程度吧！）

不想占用主题库资源可以点这里