## 1. Abridged Problem Statement

Given n boundary points (x_i, y_i), x_i strictly increasing, that trace the intersection of Red's straight-line path from the castle (point 1) to the village (point n) with the terrain profile. Red walks along this path. On terrain-exposed (above-ground) slope segments he moves at speed vw; when the path lies strictly inside a mountain (under the terrain), he may tunnel horizontally at speed vc. Compute the minimum total time to travel from the first to the last point along this path.

---

## 2. Detailed Editorial

We number the boundary points from 0 to n-1. Between consecutive boundary points i-1->i, the path lies either on the mountain's surface or inside rock. Two move-modes:
- Surface walking along the sloped segment at speed vw.
- Horizontal tunneling at speed vc, but only inside a mountain. A horizontal tunnel at height y can start at any boundary point j, provided that the horizontal line y = y_i passes through the mountain region between points j and j+1.

Define dp[i] = minimum time to reach boundary point i. Transitions:

a) Walk from i-1:
   dp[i] = dp[i-1] + length(i-1->i) / vw.

b) Tunnel ending at i from some earlier boundary j < i:
   - Check if y_i lies between y_j and y_{j+1} (the segment j->j+1 spans height y_i).
   - Compute the intersection point I on segment j->j+1 at height y = y_i by linear interpolation.
   - Walk along slope from boundary j to I at speed vw: d1 = dist((x_j, y_j), (x_I, y_i))
   - Tunnel horizontally from I to (x_i, y_i) at speed vc: d2 = |x_i - x_I|
   - dp[i] = min(dp[i], dp[j] + d1/vw + d2/vc).
   - As soon as y_j <= y_i, further j will lie outside that mountain—break.

c) By symmetry, one can also consider tunnels starting at i and ending at some future boundary j > i. This updates dp[j] similarly and ensures all horizontal shortcuts are considered in both directions.

Since each index i only loops backward (or forward) until the current mountain's lower boundary, the amortized complexity is O(n^2) in the worst case but quite efficient for n <= 1000.

---

## 3. C++ Solution

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

---

## 4. Python Solution

```python
import sys
import math

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    vw = float(next(it))
    vc = float(next(it))
    pts = [(float(next(it)), float(next(it))) for _ in range(n)]

    # dp[i]: min time to reach boundary point i
    dp = [1e18] * n
    dp[0] = 0.0

    for i in range(n):
        xi, yi = pts[i]

        # 1) Walk along adjacent slope
        if i > 0:
            x0, y0 = pts[i-1]
            d = math.hypot(xi - x0, yi - y0)
            dp[i] = min(dp[i], dp[i-1] + d / vw)

        # 2) Tunnel in from any earlier j
        #    Stop when the terrain dips below yi.
        for j in range(i-1, -1, -1):
            xj, yj   = pts[j]
            xj1, yj1 = pts[j+1]
            lo, hi = min(yj, yj1), max(yj, yj1)

            if lo <= yi <= hi:
                # Compute intersection I on segment j->(j+1) at height yi
                if yj1 != yj:
                    slope = (xj1 - xj) / (yj1 - yj)
                    xI = xj + slope*(yi - yj)
                else:
                    xI = xj1
                # Walk from (xj,yj) to I
                d1 = math.hypot(xI - xj, yi - yj)
                # Tunnel from I to (xi, yi)
                d2 = abs(xi - xI)
                dp[i] = min(dp[i], dp[j] + d1/vw + d2/vc)

            # Once yj <= yi, no further mountains cover yi from the left
            if yj <= yi:
                break

        # 3) Tunnel out to any future k
        for k in range(i+1, n):
            xk, yk   = pts[k]
            xkm, ykm = pts[k-1]
            lo, hi = min(ykm, yk), max(ykm, yk)

            if lo <= yi <= hi:
                # Intersection I at height yi on segment (k-1)->k
                if yk != ykm:
                    slope = (xk - xkm) / (yk - ykm)
                    xI = xkm + slope*(yi - ykm)
                else:
                    xI = xkm
                # Walk from I to (xk, yk)
                d1 = math.hypot(xk - xI, yk - yi)
                # Tunnel from (xi, yi) to I
                d2 = abs(xI - xi)
                dp[k] = min(dp[k], dp[i] + d1/vw + d2/vc)

            # Once yk <= yi, no further coverage
            if yk <= yi:
                break

    # Print result for last point
    print(f"{dp[n-1]:.10f}")

if __name__ == "__main__":
    main()
```

---

## 5. Compressed Editorial

- Use DP over the n boundary points: dp[i] = min time to reach point i.
- Two move-modes: slope walking (only between adjacent points) at speed vw, and horizontal tunneling inside mountains at speed vc.
- For each i, update dp[i] via dp[i-1] + slope_length/vw, and via tunnels from any j<i whose segment (j,j+1) spans y_i: walk j->intersection/vw then tunnel ->i/vc. Similarly propagate tunnels forward to j>i.
- Early breaks when terrain height falls below y_i ensure O(n^2) works for n<=1000.
