CFR 703 C. Chris and Road ( Ad hoc )

Problem - C - Codeforces
Since the points are already given in a convex-hull fashion, where vertices are given in counter-clockwise order, things are simple. There are 2 cases we need to differentiate. First, if the pedestrian can simply walk in his full speed without stopping and not encounter the bus, it definitely will be the fastest. Therefore we will check if that is possible, which can be implemented by checking whether each vertex reached the y-axis after the pedestrians had past. However, if that is not possible, the pedestrian must wait at some vertices. This process can be tracked by recording the minimum time for the pedestrian to reach each vertex's y-coordinate. We will start from the bottom-right-most vertex, going up until the gradient of the slope between the current vertex and the next becomes negative ( or vertical ). The transition will be that the minimum time for pedestrian to reach the next vertex be max( time( next vertex reaches y-axis, minimum time for pedestrian be at current vertex + time( full speed walking from current to next vertex ) ).

const int MAXN = 1e4 + 4;

int N, W, V, U;
vector< pii > vp;

bool no_obstacle(){
    for( int i = 0; i < N; ++i ){ // check if when each vertex on polygon hits y-axis, pedestrian has already passed
        double pt = 1.0 * vp[ i ].first / V;
        double y = pt * U;
        if( y < vp[ i ].second ) return false;
    }
    return true;
}

void solve(){
    cin >> N >> W >> V >> U;

    vp = vector< pii >( N );
    for( int i = 0; i < N; ++i )
        cin >> vp[ i ].first >> vp[ i ].second;

    if( no_obstacle() ){ // if can go without pausing, then go
        double ans = 1.0 * W / U;
        cout << fixed << setprecision( 8 ) << ans << "\n";
        return;
    }

    int z = 0; // get bottom-right-most vertex
    for( int i = 1; i < N; ++i )
        if( vp[ i ].second < vp[ z ].second or
            ( vp[ i ].second == vp[ z ].second and vp[ i ].first > vp[ z ].first ) )
            z = i;

    double ans = max( 1.0 * vp[ z ].second / U, 1.0 * vp[ z ].first / V ); // either pedestrian walks to slow or needs waiting the vertex
    for( ; ; ){
        int nz = z + 1 >= N ? 0 : z + 1;
        if( vp[ nz ].first <= vp[ z ].first ){ // no more obstacles
            ans += ( 1.0 * W - vp[ z ].second ) / U;
            break;
        }
        double pt = 1.0 * vp[ nz ].first / V; // the time when next vertex reaches y-axis
        double ut = ( 1.0 * vp[ nz ].second - vp[ z ].second ) / U; // how much time to travel to next vertex
        ans = max( ans + ut, pt ); // either just walking to there is longer, or needs waiting the next vertex
        z = nz;
    }
    cout << fixed << setprecision( 8 ) << ans << "\n";
}