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

· · 题解

看各位大佬在力变向或力大小过小时减小步伐，有点麻烦，本蒟蒻来一个步伐固定减小的方法：

对力进行正交分解，如果力不为0，直接把位移长度设为0~步伐间的随机数，无需考虑原本力的大小。

当然，这个方法的调参有点玄学……

再注意一下常数与浮点精度，就AC啦！(最慢点328ms)

以下是代码(写得很有点奇怪)

#include<bits/stdc++.h>
using namespace std;
#define F(i) for(int i=0;i<n;i++)
const double eps=1e-10;
inline int cmp(double x,double y=0){
    if(fabs(x-y)<eps)return 0;
    return x>y?1:-1;
}
inline double sqr(double x){
    return x*x;
}
inline double dis(double x,double y){
    return sqrt(sqr(x)+sqr(y));
}
double x[1010],y[1010],w[1010];
int main(){
    int n;
    cin>>n;
    F(i)cin>>x[i]>>y[i]>>w[i];
    double sum=0.0;
    double sx=0,sy=0;
    F(i)sum+=w[i];
    F(i)sx+=x[i]*w[i];
    double avgx=sx/sum;//平均X坐标
    F(i)sy+=y[i]*w[i];
    double avgy=sy/sum;//平均Y坐标
    F(i)w[i]/=sum;//质量归一化
    double nx=avgx,ny=avgy;//坐标
    double t=20.0;//步伐大小
    //int dog=0;(循环计数器，控制常数)
    while(t>1e-8){
        //dog++;
        double fx=0,fy=0;//普通的力
        double mf=0;//往洞里拉的力
        F(i){
            double dx=x[i]-nx,dy=y[i]-ny;
            if(cmp(dis(dx,dy))==0)
                mf+=w[i];//往洞里拉
            else{
                double d1=1.0/dis(dx,dy)*w[i];//减少计算量
                fx+=dx*d1;
                fy+=dy*d1;
            }
        }
        double sf=dis(fx,fy);
        //printf("mf=%.3lf fx=%.3lf fy=%.3lf\n",mf,fx,fy);
        if(cmp(mf,sf)>=0){
            //   洞里的力大于等于向外拉的力:卡洞里
            //or 此刻受力为0:就是这里
            t=0;
            break;
        }
        double b=t*t*((double)rand()/RAND_MAX)/sf;
        fx*=b;
        fy*=b;
        nx+=fx;
        ny+=fy;
        t*=0.9995;//每次步伐都乘0.9995
    }        
    //cout<<dog<<endl;
    printf("%.3lf %.3lf",nx,ny);
}