せっかくDE解けたのにCが間に合わず。
https://www.hackerrank.com/contests/101hack47/challenges/basketball-game
問題
バスケットボールを考える。
2次元座標上のコートにおいて、ボールを持った選手とゴールの位置が与えられる。
選手がボールを投げると、ゴールに対し等速直線運動でボールが飛んでいく。
ここで、相手チームの5名の選手の位置と移動速度が与えられる。
相手チームの選手が最適に動いたとき、ボールが相手チームの選手に触れられることなくゴールに到達可能か判定せよ。
解法
相手チームの各選手がボールに触れるか、個別に判定しよう。
愚直に幾何の問題を解こうとしてもよい。その場合2次方程式を解くことになる。
自分は一発で答えだそうとしてうまく式が作れず、三分探索にした。
f(t) := 時間t到達後にボールが到達する位置に対し、選手が移動しようとするとどれだけ余裕があるか
Tをボールがゴールに到達する時刻とすると、f(t)≧0となるt＜Tがあればよい。
f(t)は上に凸になるので、三分探索で絞り込み可能。
int T; double XH,YH; double XC,YC,VC; double X,Y,V; double dist(double t) { double cx=XH-XC; double cy=YH-YC; double C=hypot(cx,cy); cx/=C; cy/=C; double tx=XC+cx*t*VC; double ty=YC+cy*t*VC; double dx=tx-X; double dy=ty-Y; return t*V-hypot(dx,dy); } int ok() { double a=hypot(X-XH,Y-YH)/V; double b=hypot(XC-XH,YC-YH)/VC; if(b<1e-9) return 1; if(a<b-1e-9) return 0; double L=0,R=b; int i; FOR(i,200) { double M1=(2*L+R)/3; double M2=(L+2*R)/3; double v1=dist(M1); double v2=dist(M2); if(v1>1e-9 || v2>1e-9) return 0; if(v1<v2) L=M1; else R=M2; } return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>XH>>YH; cin>>XC>>YC>>VC; string R="YES"; FOR(i,5) { cin>>X>>Y>>V; if(ok()==0) R="NO"; } cout<<R<<endl; } }
まとめ
ベクトルをこねくりまわしてタイムロス。
