mayoko’s diary

プロコンとかいろいろ。

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

問題

codeforces.com

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