Codeforces Round #365 (Div. 2) C. Chris and Road
問題
Problem - C - Codeforces
N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題
解法
バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く,そうでなければスタート地点を後ろにずらしていき直線がバスに接するようにすればいい.
移動後の直線をとすると,すべての点に対してを求めればよくなる.下図の緑の直線の場合,待つ必要はなくなる.
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define GET_ARG(a,b,c,F,...) F #define REP3(i,s,e) for (i = s; i <= e; i++) #define REP2(i,n) REP3 (i,0,(int)(n)-1) #define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__) int main(void) { int i, N, W; double V, U; cin >> N >> W >> V >> U; double x = 0; bool go = true; REP (i,N) { int X, Y; cin >> X >> Y; x = max(x,U/V*X-Y); if (X / V < Y / U) go = false; } if (go) x = 0; cout << fixed << setprecision(7); cout << (W + x) / U << endl; return 0; }