SRM 440 DIV1 Easy - IncredibleMachine (復習××)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10310&rd=13748

ある惑星上にて(x、y)からなる点が複数与えられる。
その惑星の重力gは不明だが、すべての点を順番に通った時の合計時間Tはわかっている。

また、1つの点から次の点までの距離dは以下の式で計算される。
d=v0*t+0.5*a*t
ここでtは2点間の移動に必要な時間、a=g*sinで表わされる。
v0は速度であり次の点に移ったときの速度はv1=v0+a*tで表わされる。

このとき、その惑星の重力gを求める。

解き方


gが決まればそのときの合計時間T(g)は一意に求めることができる。

つまり、二分探索で解くことができる。

コード


class IncredibleMachine {

public:

double calc(vector<int> x,vector<int> y,double g){
double ret=0.0;
double v0=0.0;
FORE(i,0,x.size()-1){
double d=sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]));
double a=g*abs(y[i]-y[i+1])/d;
double t=(-v0+sqrt(v0*v0+2.0*a*d))/a;
v0+=a*t;
ret+=t;
}
return ret;
}

double gravitationalAcceleration(vector<int> x, vector<int> y, int T) {
double low=0.0,high=1e+9;

FORE(i,0,200){
double mid=(low+high)/2.0;
if(calc(x,y,mid)<T)high=mid;
else low=mid;
}

return high;
}

};
このエントリーをはてなブックマークに追加