p445.ans1
======================
50.0

=================
p445.ans2
======================
100.0

=================
p445.ans3
======================
70.710678


=================
p445.ans4
======================
150.0

=================
p445.ans5
======================
106.066017

=================
p445.ans6
======================
100.0

=================
p445.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
long double vw, vc;
vector<pair<long double, long double>> points;

void read() {
    cin >> n >> vw >> vc;
    points.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> points[i];
    }
}

void solve() {
    // Red moves along the terrain polyline at walking speed vw, but may also
    // tunnel horizontally through a mountain at speed vc. We do a DP over the
    // vertices, where dp[i] is the minimum time to reach point i.
    //
    // From point i we relax along the surface to the next vertex i+1 (walking).
    // For a horizontal tunnel at height y_i we look for the points where the
    // horizontal line y = y_i crosses the polyline. Scanning leftwards over
    // segments (j, j+1) we find an entry crossing, walk from point j down to
    // that crossing, then tunnel horizontally to (x_i, y_i); scanning
    // rightwards over segments (j-1, j) we tunnel from (x_i, y_i) to a crossing
    // and walk up to point j. We stop each scan once a vertex no taller than
    // y_i is reached, since the line cannot re-enter the mountain past it.
    //
    // The horizontal crossing x is found by linear interpolation along the
    // segment; degenerate horizontal segments are handled separately. The
    // answer is dp[n-1].

    vector<long double> dp(n, 1e12);
    dp[0] = 0.0;

    for(int i = 0; i < n; i++) {
        auto [x, y] = points[i];
        if(i > 0) {
            auto [x_prev, y_prev] = points[i - 1];
            dp[i] =
                min(dp[i], dp[i - 1] + sqrt(
                                           (x - x_prev) * (x - x_prev) +
                                           (y - y_prev) * (y - y_prev)
                                       ) / vw);
        }

        for(int j = i - 1; j >= 0; j--) {
            auto [x_prev, y_prev] = points[j];
            auto [x_prev_next, y_prev_next] = points[j + 1];

            long double up = max(y_prev, y_prev_next);
            long double down = min(y_prev, y_prev_next);

            if(down <= y && y <= up) {
                long double slope_x =
                    y_prev_next == y_prev
                        ? 0.0
                        : (x_prev_next - x_prev) / (y_prev_next - y_prev);
                long double intersection_x = x_prev + slope_x * (y - y_prev);
                if(y_prev_next == y_prev) {
                    intersection_x = x_prev_next;
                }

                long double dist_intersection_to_prev = sqrt(
                    (x_prev - intersection_x) * (x_prev - intersection_x) +
                    (y_prev - y) * (y_prev - y)
                );

                dp[i] =
                    min(dp[i], dp[j] + dist_intersection_to_prev / vw +
                                   (x - intersection_x) / vc);
            }

            if(y_prev <= y) {
                break;
            }
        }

        for(int j = i + 1; j < n; j++) {
            auto [x_next, y_next] = points[j];
            auto [x_next_prev, y_next_prev] = points[j - 1];

            long double up = max(y_next, y_next_prev);
            long double down = min(y_next, y_next_prev);

            if(down <= y && y <= up) {
                long double slope_x =
                    y_next_prev == y_next
                        ? 0.0
                        : (x_next - x_next_prev) / (y_next - y_next_prev);
                long double intersection_x =
                    x_next_prev + slope_x * (y - y_next_prev);
                long double dist_intersection_to_next = sqrt(
                    (x_next - intersection_x) * (x_next - intersection_x) +
                    (y_next - y) * (y_next - y)
                );

                dp[j] =
                    min(dp[j], dp[i] + dist_intersection_to_next / vw +
                                   (intersection_x - x) / vc);
            }

            if(y_next <= y) {
                break;
            }
        }
    }

    cout << setprecision(10) << fixed << dp.back() << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p445.in1
======================
3
1 2
0 0
50 50
100 0

=================
p445.in2
======================
3
1 1
0 0
50 50
100 0

=================
p445.in3
======================
3
2 1
0 0
50 50
100 0

=================
p445.in4
======================
6
1 2
0 0
50 50
100 0
150 0
200 50
250 0

=================
p445.in5
======================
3
2 1
0 0
100 100
150 50

=================
p445.in6
======================
2
1 2
0 0
100 0

=================
statement.txt
======================
445. Dig or Climb
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Benjamin Forest VIII is a king of a country. One of his best friends Nod lives in a village far from his castle. Nod gets seriously sick and is on the verge of death. Benjamin orders his subordinate Red to bring good medicine for him as soon as possible. However, there is no road from the castle to the village. Therefore, Red needs to climb over mountains and across canyons to reach the village. He has decided to get to the village on the shortest path on a map, that is, he will move on the straight line between the castle and the village. Then his way can be considered as polyline with n points (x1, y1)... (xn, yn) as illustlated in the following figure.

Here, xi and yi are coordinates of point i. The castle is located on the point (x1, y1), and the village is located on the point (xn, yn). Red can walk with speed vw. Also, since he has a skill to cut a tunnel through a mountain horizontally, he can move strictly inside the mountain with speed vc. Your job is to write a program to find the minimum time to get to the village.
Input
The input is given in the following format: n vw vc x1 y1 ... xn yn You may assume all the following: 1 ≤ n ≤ 1000, 1 ≤ vw, vc ≤ 10, -10000 ≤ xi, yi ≤ 10000, and xi < xj for all i < j.
Output
You should print the minimum time required to get to the village in a line. Each minimum time should be given as a decimal with an arbitrary number of fractional digits and with an absolute error of at most 10-6.
Example(s)
sample input
sample output
3
2 1
0 0
50 50
100 0
70.710678

sample input
sample output
3
1 1
0 0
50 50
100 0
100.000000

sample input
sample output
3
1 2
0 0
50 50
100 0
50.000000

sample input
sample output
3
2 1
0 0
100 100
150 50
106.066017

sample input
sample output
6
1 2
0 0
50 50
100 0
150 0
200 50
250 0
150.000000

sample input
sample output
2
1 2
0 0
100 0
100.000000

=================
