kmjp's blog

競技プログラミング参加記です

101 Hack 47 : C. Basketball Game

せっかく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;
	}
}

まとめ

ベクトルをこねくりまわしてタイムロス。

広告を非表示にする