Codeforces Round #365 (Div. 2) C. Chris and Road
問題
n 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。
y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。
解法
凸多角形の左側を歩くときと右側を歩くときで場合分けします。右側を歩くのは必ず成功するので, これでちゃんと答えが求められます。
左側を歩く場合, x 軸が最小になる点から y 軸が最大になる点(時計の 9 時方向から 12 時方向ってイメージ)で凸多角形に衝突しなければ良いです。
右側を歩く場合, y 軸が最小になる点から x 軸が最大になる点(時計の 6 時方向から 3 時方向)で凸多角形の内部に入らないようにすれば良いです。
const int MAXN = 100100; pii P[MAXN]; int N, W, V, U; typedef double Real; int prv(int i) { return (i+N-1)%N; } int nxt(int i) { return (i+1)%N; } int main() { cin >> N >> W >> V >> U; for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second; int imin = min_element(P, P+N) - P; int imax = max_element(P, P+N) - P; Real ans = 1e18; // 多角形の左側を通る場合 { int i = imin; bool ng = false; for (int j = 0; j < N; j++) { Real t = (Real)P[i].second / U; Real x = P[i].first - V*t; if (x < 0) { ng = true; break; } int ni = prv(i); if (P[ni].second <= P[i].second) break; i = ni; } if (!ng) ans = min(ans, (Real)W/U); } // 多角形の右側を通る場合 { while (1) { int ni = prv(imax); if (P[ni].second >= P[imax].second) break; imax = ni; } Real tmp = 0; int y = 0; int i = imax; for (int j = 0; j < N; j++) { // 普通に歩いてかかる時間 Real need = (Real)(P[i].second - y) / U; if ((Real)P[i].first - V*(tmp+need) <= 0) tmp += need; else tmp = (Real)P[i].first / V; y = P[i].second; int ni = nxt(i); if (P[ni].first <= P[i].first) break; i = ni; } tmp += (Real)(W-y)/U; ans = min(ans, tmp); } printf("%.10lf\n", ans); return 0; }