Codeforces #365 Div2 C. Chris and Road

割とグダグダな出来だったはずだけど、なんか割と上位陣が落ちてDiv2では自己ベスト順位に。
http://codeforces.com/contest/703/problem/C

問題

２次元座標上でX軸と平行な幅Wの道路があるとする。
歩行者がこの道路を横断する形で、(0,0)から(0,W)までY軸上を移動する。
最高速度はUまで上げることができるが、常に最高速度で動く必要はない。

ここで、多角形が与えられる。
この多角形は時速Vで道路にそってX軸の負の方向に動く。
歩行者が多角形に衝突しないように移動する場合、(0,W)に到達する最短時間を求めよ。

解法

歩行者と多角形が同時に動くと考えるとややこしいので、歩行者がy=(U/V)x上を動くと考えよう。
この直線と多角形が衝突しない場合、歩行者は常時最高速度で動けばよい。

そうでない場合、y=(U/V)(x-a)が多角形と交わらないような最小のaを求めよう。
すると多角形がaだけ移動してから歩行者が動き始めればよいことが分かる。

int N;
ll W,V,U;
ll X[101010],Y[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W>>V>>U;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	int up=0,down=0;
	FOR(i,N) {
		if(Y[i]*V-X[i]*U>0) up++;
		if(Y[i]*V-X[i]*U<0) down++;
	}
	
	if(up==0 || down==0) return _P("%.12lf\n",W/1.0/U);
	double ma=0;
	FOR(i,N) if(X[i]>=0) ma=max(ma,max(X[i]*1.0/V,Y[i]*1.0/U) + (W-Y[i])*1.0/U);
	_P("%.12lf\n",ma);
}

まとめ

面倒な幾何かとおもったらそこまでではなかった。