BZOJ3680 吊打XXX
传送门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
*/