h_nosonの日記

競プロ、CTFなど

Codeforces Round #365 (Div. 2) C. Chris and Road

問題

Problem - C - Codeforces
N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題

解法

バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く,そうでなければスタート地点を後ろにずらしていき直線がバスに接するようにすればいい.
移動後の直線をy=U/V*x-bとすると,すべての点に対してb=\max(b,U/V*x-y)を求めればよくなる.下図の緑の直線の場合,待つ必要はなくなる.
f:id:h_noson:20160805150303p:plain

ソースコード

#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;
}