题解 P1337 【[JSOI2004]平衡点 / 吊打XXX】

· · 题解

目前最短代码，没有之一

(其他人行数看不到，但550B的代码量在本题的AC记录里是妥妥rank1的（绝大多数都在1000B以上），而且时效也不差（28~29ms）)

好了，下面步入正题

本题用不着任何玄学算法，每次给绳结算一下合力，然后沿着合力方向移动一下。

因为绳结不断移动的过程中，系统是不断趋向平衡的，因此每次移动的长度会不断缩小，当移动长度缩小到无法改变最终结果时输出当前位置，结束

这样也省的算重力势能啥的了（事实上初二下物理都没学的我也不会）

当然，你说你厉害，用SA,PSO这些算法能吊打我……怎么说呢，个人想要时间复杂度和编程复杂度都小，你要是觉得这样有意思，我也无话可说

最后，附上25行的代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define E(x) ((x)*(x))
const int N=1009;
int n,px[N],py[N],pw[N];
double x,y,lon=10000.0;//初始移动长度
void move(double l){
    double sx=0,sy=0,g;
    for(int i=1;i<=n;i++){//将绳结上的力正交分解，横向的加给sx，纵向加给sy
        g=sqrt(E(px[i]-x)+E(py[i]-y));
        if(g==0)continue;
        sx+=pw[i]/g*(px[i]-x);
        sy+=pw[i]/g*(py[i]-y);
    }
    g=sqrt(sx*sx+sy*sy);//算出合力大小
    x+=l/g*sx,y+=l/g*sy;//向合力方向移动l
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&px[i],&py[i],&pw[i]);
    while(lon>4e-4)
        move(lon),lon*=0.618;//lon乘多少随你定，不是太小都能过
    printf("%.3f %.3f\n",x,y),exit(0);
}

告辞