BZOJ 3680吊打XXX

原題リンク:http://www.lydsy.com/JudgeOnline/problem.php?id=3680 洛谷リンク:https://www.luogu.org/problemnew/show/P1337
吊打XXX
Description
gtyはまた試合を虐待し、虐待されたこんにゃくたちはgtyを吊るすことにした.gtyは大勢が機知に富んでいないのを見てn個の分身を分けたが、やはり人の多いコンニャクに捕まえられた.こんにゃくたちはn個のgtyをn本のロープに吊り下げ、それぞれのロープが天台の穴を通った.このn本のロープには共通のロープがある.gtyを吊り下げた後、コンニャクたちはgtyごとに重力が異なるため、縄の結び目xが移動していることを発見した.こんにゃくwangxz脳洞の大開の決定はxの最後の滞在先の座標を計算し、彼が弱すぎるのであなたに助けを求めることにした.摩擦にかかわらず、エネルギー損失にかかわらず、gtyは十分に低いので地面に落ちることはありません.
Input
第1の動作の正の整数n(1<=n<=10000)を入力し、gtyの数を表す.次にn行、各行の3つの整数xi,yi,wiは、i番目のgtyの横座標、縦座標、重力を表す.20%のデータに対してgtyは直線に配列されている.50%のデータに対して、1<=n<=1000.100%のデータに対して、1<=n<=10000、-10000<=xi、yi<=10000
Output
1行2個の浮動小数点数(小数点以下3桁まで保持)を出力し、最終xの横、縦座標を表す.
Sample Input
3 0 0 1 0 2 1 1 1 1
Sample Output
0.577 1.000
問題を解く
この問題は[JSOI 2004]平衡点が背景を変えて、山に登るアルゴリズムの板の問題です.  山登りは有名なランダム演算アルゴリズムで、啓発的な検索に似ていて、空間内で最適解を探しています.この問題には局所最適解がないので,山登りアルゴリズムは十分であり,シミュレーションアニーリングは必要ない.しかし、ブロガーは書くときも温度(t)変数を導入し、最後のコードは両者の結合体に属しており、みんなが読めばいい.始点はランダムに生成され,現在のノードにバランスがなければ,t単位を合力方向に移動し,このtは移動回数とともに徐々に減少するので,ノードは徐々に安定し最適解に近づく.
コード

#include
#define db double
using namespace std;
const int M=10005;
struct pt{db x,y;int w;};
db sqr(db x){return x*x;}
db dis(pt a,pt b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
int n,r,f;
char c;
pt p[M],ans;
int read()
{
    r=0;f=1;
    c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}
void in()
{
    ans.x=ans.y=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    p[i].x=read(),p[i].y=read(),p[i].w=read(),ans.x+=p[i].x*p[i].w,ans.y+=p[i].y*p[i].w;
    ans.x/=n;ans.y/=n;
}
void ac()
{
    db t=1e8,x,y,d;
    while(t>1e-8)
    {
        x=y=0;
        for(int i=1;i<=n;++i)
        {
            d=dis(p[i],ans);
            x+=p[i].w*(p[i].x-ans.x)/d;
            y+=p[i].w*(p[i].y-ans.y)/d;
        }
        ans.x+=x*t;ans.y+=y*t;
        if(t>0.5)t/=2;
        else t*=0.97;
    }
    printf("%.3lf %.3lf",ans.x,ans.y);
}
int main()
{
    in();ac();
    return 0;
}