BZOJ3680 吊打XXX

Published on 2017 Jul 11 09:09:49
Last Updated on 2017 Jul 12 10:04:58

传送门
5W 1A
爬山法裸题，但是我没用爬山法，用的是力的方法
具体是求出n个物体对当前点的合力，再往合力方向走一段距离，这个距离逐渐缩小
似乎黄学长也用的是这种方法。。。但是他管这叫爬山法QAQ

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
double forcetime=1000;
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
}pt[N],np;
double w[N];
int n;
typedef Point Vector;
Vector operator-(Point a,Point b){
    return Vector(a.x-b.x,a.y-b.y);
}
Vector operator+(Vector a,Vector b){
    return Vector(a.x+b.x,a.y+b.y);
}
Vector operator*(double a,Vector b){
    return Vector(a*b.x,a*b.y);
}
double mod(Vector x){
    return hypot(x.x,x.y);
}
void upd(){
    Vector F(0,0);
    for(int i=1;i<=n;i++){
        Vector dir=pt[i]-np;
        double len=mod(dir);
        if(abs(len)<1e-9) continue;
        F=F+((w[i]/len)*dir);
    }
    np=np+((forcetime)*F);
}

int main(){
    scanf("%d",&n);
    double ptxs=0,ptys=0,ws=0;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf",&pt[i].x,&pt[i].y,&w[i]);
        ptxs+=pt[i].x*w[i];
        ptys+=pt[i].y*w[i];
        ws+=w[i];
    }
    np=Point(ptxs/n,ptys/n);
    while(forcetime>0.00000001){
        upd();
        if(forcetime>0.5) forcetime/=2.; //之前一直没加这句，调了半个小时QAQ
        else forcetime*=0.97;
    }
    printf("%.3lf %.3lf",np.x,np.y);
}  
/*
3
0 0 1
0 2 1
1 1 1
*/