Article From:https://www.cnblogs.com/luyouqi233/p/9121955.html

https://www.lydsy.com/JudgeOnline/problem.php?id=3680

https://www.luogu.org/problemnew/show/P1337

There are n weights, each of which is tied to a long enough rope. Each piece of string goes through the hole on the table from top to bottom and then is tied together. The X is a common knot in the picture. Assuming that the rope is completely elastic (no energy loss), the table is high enough (so the weight will not drop to the ground) and ignore it.Some friction.

Ask where the knot X is finally balanced.

Note: the holes on the desktop are much smaller than the knot X, so even if a heavy weight is particularly heavy, the knot X can’t go through the hole on the desktop, most of which is stuck at a hole.

Learn to do a mess.

When the whole system is stable, its energy is the smallest, and the energy depends on the height and weight of each item.

The greater the value, the greater the energy.

Of course, the height of the table = the height of the table – the length of the rope + item to the node distance s, the first two are constant, so the s* weight can be replaced, the greater the value, the greater the energy.

So we took a simulated annealing and tried to find the smallest point.

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long double dl;
const int N=1e4+5;
const dl T=13570;
const dl eps=1e-15;
const dl delta=0.99;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct iron{
    dl x,y,w;
}a[N];
int n;
dl xx,yy,t,ans=9e18;
inline dl suan(dl x,dl y){
    dl res=0;
    for(int i=1;i<=n;i++){
    dl dx=x-a[i].x,dy=y-a[i].y;
    dl dis=sqrt(dx*dx+dy*dy);
    res+=dis*a[i].w;
    }
    return res;
}
void simulate_anneal(){
    t=T;
    while(t>eps){
    dl nx=xx+(rand()*2-RAND_MAX)*t;
    dl ny=yy+(rand()*2-RAND_MAX)*t;
    dl nans=suan(nx,ny);
    dl dans=nans-ans;
    if(dans<-eps){
        xx=nx;yy=ny;ans=nans;
    }else if(rand()<exp(-dans/t)*RAND_MAX){
        xx=nx;yy=ny;
    }
    t*=delta;
    }
}
int main(){
    srand(19260817);
    n=read();
    for(int i=1;i<=n;i++){
    a[i].x=read(),a[i].y=read(),a[i].w=read();
    xx+=a[i].x,yy+=a[i].y;
    }
    xx/=n,yy/=n;
    simulate_anneal();
    printf("%.3Lf %.3Lf\n",xx,yy);
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

 +The author of this article: luyouqi233. +

 +Welcome to my blog: http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *