Codeforces #327 Div1 B. Chip 'n Dale Rescue Rangers

本番通ったけどだいぶ無駄なコード書いた。
http://codeforces.com/contest/590/problem/B

問題

２次元座標上で、初期状態(X1,Y1)から(X2,Y2)に移動したい。
移動は飛行船で行うので風の影響を受ける。

風の速度と飛行船が速度の相対速度は、その大きさがV以下でなければならない。
出発後、最初時間Tは(Vx,Vy)の速度で風が吹き、以降は(Wx,Wy)で風が吹く。
目的地に移動する最短時間はいくらか。

解法

かかる時刻がtとする。
飛行船が風の速度と同じ向きに移動した場合の位置は(X1+min(T,t)*Vx+max(0,t-T)*Wx,Y1+min(T,t)*Vy+max(0,t-T)*Wy)である。
ここから(X2,Y2)までの距離がV*t以内なら目的地に到達可能である。

風の速度はV未満なので、時間経過に伴い到達可能な範囲は単純に増加するので、tを二分探索すればよい。

int X,Y;
int V,T;
int VX,VY,WX,WY;

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>x>>y>>X>>Y;
	X-=x;
	Y-=y;
	cin>>V>>T;
	cin>>VX>>VY>>WX>>WY;
	
	double L=0,R=1e9;
	FOR(i,200) {
		double M=(L+R)/2;
		double cx = min(1.0*T,M)*VX + max(0.0,M-T)*WX;
		double cy = min(1.0*T,M)*VY + max(0.0,M-T)*WY;
		
		if((X-cx)*(X-cx)+(Y-cy)*(Y-cy)<=V*M*V*M) R=M;
		else L=M;
	}
	
	return _P("%.12lf\n",L);

}

まとめ

本番無駄にT以内で到達するか二次方程式解いちゃった。