Project Euler

Mountain Range

The elevation at point (x, y) is given by h(x,y) = (5000 - 0.005(x^2 + y^2 + xy) + 12.5(x+y)) * e^(-|0.000001(x^2+y^2) - 0.0015(x+y) + 0.7|). A mosquito wants to fly from A = (200, 200) to B = (140...

Source sync Apr 19, 2026

Problem #0262

Level Level 16

Solved By 863

Languages C++, Python

Answer 2531.205

Length 651 words

geometrymodular_arithmeticoptimization

The following equation represents the continuous topography of a mountainous region, giving the elevation $h$ at any point $(x, y)$: \[h = \left (5000 - \frac {x^2 + y^2 + xy}{200} + \frac {25(x + y)}2\right ) \cdot e^{-\left |\frac {x^2 + y^2}{1000000} - \frac {3(x + y)}{2000} + \frac 7 {10}\right |}.\] A mosquito intends to fly from $A(200,200)$ to $B(1400,1400)$, without leaving the area given by $0 \le x, y \le 1600$.

Because of the intervening mountains, it first rises straight up to a point $A^\prime $, having elevation $f$. Then, while remaining at the same elevation $f$, it flies around any obstacles until it arrives at a point $B^\prime $ directly above $B$.

First, determine $f_{\mathrm {min}}$ which is the minimum constant elevation allowing such a trip from $A$ to $B$, while remaining in the specified area.

Then, find the length of the shortest path between $A^\prime $ and $B^\prime $, while flying at that constant elevation $f_{\mathrm {min}}$.

Give that length as your answer, rounded to three decimal places.

Note: For convenience, the elevation function shown above is repeated below, in a form suitable for most programming languages:

$h=( 5000-0.005*(x*x+y*y+x*y)+12.5*(x+y) ) * \exp ( -\operatorname {abs}(0.000001*(x*x+y*y)-0.0015*(x+y)+0.7) )$

Problem 262: Mountain Range

Mathematical Development

Theorem 1 (Symmetry). The elevation function satisfies $h(x, y) = h(y, x)$ for all $(x, y) \in \mathbb{R}^2$ . Consequently, the landscape is symmetric about the line $y = x$ .

Proof. Both the polynomial factor $P(x,y) = 5000 - 0.005(x^2 + y^2 + xy) + 12.5(x + y)$ and the exponent $g(x,y) = 0.000001(x^2 + y^2) - 0.0015(x + y) + 0.7$ involve only the symmetric expressions $x^2 + y^2$ , $xy$ , and $x + y$ . Since $P(x,y) = P(y,x)$ and $g(x,y) = g(y,x)$ , we have $h(x,y) = h(y,x)$ . $\square$

Theorem 2 (Mountain ridge structure). Define $g(x,y) = 0.000001(x^2 + y^2) - 0.0015(x + y) + 0.7$ . The zero set $\mathcal{C} = \{(x,y) : g(x,y) = 0\}$ is the circle

\mathcal{C}: (x - 750)^2 + (y - 750)^2 = 425000,

of center $(750, 750)$ and radius $\sqrt{425000} \approx 651.9$ . On $\mathcal{C}$ , the exponential factor attains its maximum value $e^0 = 1$ . Away from $\mathcal{C}$ , $|g| > 0$ and the exponential decays, so the elevation is concentrated near $\mathcal{C}$ , forming an annular mountain range.

Proof. Setting $g = 0$ : $0.000001(x^2 + y^2) = 0.0015(x + y) - 0.7$ , so $x^2 + y^2 = 1500(x + y) - 700000$ . Completing the square: $(x - 750)^2 + (y - 750)^2 = 750^2 + 750^2 - 700000 = 1125000 - 700000 = 425000$ . The exponential factor $e^{-|g|}$ is maximized precisely when $|g| = 0$ , i.e., on $\mathcal{C}$ . $\square$

Theorem 3 (Minimax characterization of $f_{\min}$ ). The value $f_{\min}$ equals the minimax elevation:

f_{\min} = \inf_{\gamma \in \Gamma(A,B)} \max_{(x,y) \in \gamma} h(x,y),

where $\Gamma(A,B)$ is the set of continuous paths from $A$ to $B$ in $[0,1600]^2$ . The infimum is attained at a saddle point (pinch point) of $h$ on the mountain ridge.

Proof. Since $A = (200,200)$ lies inside the circle $\mathcal{C}$ and $B = (1400,1400)$ lies outside, any continuous path from $A$ to $B$ must cross the high-elevation ridge near $\mathcal{C}$ . The minimax elevation is the lowest value $f$ such that the sub-level set $\{h \le f\}$ contains a connected path from $A$ to $B$ . This occurs when the barrier $\{h > f\}$ ceases to separate $A$ from $B$ , which happens at a saddle point where the barrier pinches to zero width. By the symmetry of $h$ and the geometry of the domain, the relevant saddle lies on the $x$ -axis (where $y = 0$ ). Numerical optimization of $h(x, 0)$ locates the saddle at $x^* \approx 895.483$ with $f_{\min} = h(x^*, 0) \approx 10396.462$ . By symmetry, a second saddle exists at $(0, y^*)$ with $y^* \approx 895.483$ . $\square$

Theorem 4 (Shortest path structure). At elevation $f_{\min}$ , the shortest horizontal path from the vertical through $A$ to the vertical through $B$ consists of at most two straight-line segments (tangent to the contour $\{h = f_{\min}\}$ ) and arcs along the contour, threading through the pinch point.

Proof. The passable region $\{h \le f_{\min}\}$ at the critical elevation has the pinch point as a bottleneck. In a planar region bounded by a smooth curve, the shortest path between two points consists of straight-line segments in the interior and geodesic arcs along the boundary. At transition points $P$ and $Q$ , the tangency condition requires $\nabla h \perp \overrightarrow{AP}$ at $P$ and $\nabla h \perp \overrightarrow{QB}$ at $Q$ (the gradient of the constraint function is normal to the boundary, and the straight segment must be tangent to the boundary at the junction). The path is therefore:

A \to P \xrightarrow{\text{arc}} \text{pinch} \xrightarrow{\text{arc}} Q \to B.

$\square$

Editorial

h(x,y) = (5000 - 0.005*(x^2+y^2+xy) + 12.5(x+y)) A mosquito flies from A(200,200) to B(1400,1400) within 0<=x,y<=1600. It ascends to elevation f, flies horizontally at f, then descends. Find f_min (minimum elevation allowing such trip), then the shortest horizontal path at f_min, rounded to 3 decimal places. Solution approach: 1. f_min = minimax elevation = 10396.462193 (peak on y=0 boundary at x=895.483). 2. The barrier {h > f_min} is an annular (ring-shaped) region. It has a “pinch point” at (895.483, 0) where the barrier width is zero. By symmetry h(x,y)=h(y,x), another pinch exists at (0, 895.483). 3. The shortest path from A to B goes: A -> PA -> arc(PA, pinch) -> arc(pinch, Q) -> Q -> B where PA is tangent from A to the outer contour (left branch), and Q is tangent from B to the outer contour (right branch). The arc goes through the pinch point at (895.483, 0). 4. PA = (624.650, 48.254), Q = (1536.043, 873.038). 5. Path = 450.948 + 276.452 + 1259.565 + 544.239 = 2531.205. We numerically maximize h(x, 0) over x in [800, 1000] via bounded optimization. We then find tangent point P on outer-left contour branch. Finally, find tangent point Q on outer-right contour branch.

Pseudocode

Numerically maximize h(x, 0) over x in [800, 1000] via bounded optimization
Find tangent point P on outer-left contour branch:
Find tangent point Q on outer-right contour branch:
Compute total path length:
Round to 3 decimal places

Complexity Analysis

Time: $O(N)$ for contour tracing with $N$ steps; $O(\log(1/\epsilon))$ bisection iterations for tangent-point finding; $O(N)$ for arc-length integration. Total: $O(N)$ where $N$ is the contour resolution (inversely proportional to step size).
Space: $O(1)$ auxiliary storage (contour traced incrementally without storing all points).

Answer

\boxed{2531.205}

C++ project_euler/problem_262/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 262: Mountain Range
 *
 * h(x,y) = (5000 - 0.005*(x^2+y^2+x*y) + 12.5*(x+y))
 *         * exp(-|0.000001*(x^2+y^2) - 0.0015*(x+y) + 0.7|)
 *
 * Find f_min (minimax elevation A(200,200) to B(1400,1400)),
 * then shortest path at f_min through the pinch point.
 *
 * The barrier {h > f_min} is ring-shaped with a pinch at (895.483, 0).
 * f_min = max h(x,0) = h(895.483, 0) ≈ 10396.462.
 *
 * Path: A -> PA(tangent) -> arc to pinch -> arc to Q(tangent) -> B
 * PA ≈ (624.650, 48.254), Q ≈ (1536.043, 873.038)
 *
 * Approach: numerical contour tracing and tangent finding.
 *
 * Answer: 2531.205
 */

double h_func(double x, double y) {
    double t1 = x*x + y*y + x*y;
    double t2 = x*x + y*y;
    double base = 5000.0 - 0.005*t1 + 12.5*(x+y);
    double ex = fabs(0.000001*t2 - 0.0015*(x+y) + 0.7);
    return base * exp(-ex);
}

double dh_dx(double x, double y) {
    const double eps = 1e-7;
    return (h_func(x+eps, y) - h_func(x-eps, y)) / (2*eps);
}

double dh_dy(double x, double y) {
    const double eps = 1e-7;
    return (h_func(x, y+eps) - h_func(x, y-eps)) / (2*eps);
}

// Find x on contour h=f at given y, scanning from left or right
double find_contour_x(double y, double f, bool from_left) {
    double prev = h_func(from_left ? 0 : 1600, y) - f;
    int start = from_left ? 1 : 1599;
    int end = from_left ? 1601 : -1;
    int step = from_left ? 1 : -1;
    for (int xi = start; xi != end; xi += step) {
        double cur = h_func(xi, y) - f;
        if (prev * cur < 0) {
            // Bisect
            double lo = from_left ? xi-1.0 : (double)xi;
            double hi = from_left ? (double)xi : xi+1.0;
            for (int i = 0; i < 60; i++) {
                double mid = (lo+hi)/2;
                if ((h_func(mid, y) - f) * (h_func(lo, y) - f) <= 0)
                    hi = mid;
                else
                    lo = mid;
            }
            return (lo+hi)/2;
        }
        prev = cur;
    }
    return -1;
}

double trace_arc(double x0, double y0, double x1, double y1, double f, double step_size=0.05) {
    double x = x0, y = y0;
    double total = 0;
    for (int i = 0; i < 500000; i++) {
        double gx = dh_dx(x, y);
        double gy = dh_dy(x, y);
        double t1x = -gy, t1y = gx;
        double t2x = gy, t2y = -gx;
        double dx = x1-x, dy = y1-y;
        double tx, ty;
        if (t1x*dx + t1y*dy > t2x*dx + t2y*dy)
            tx = t1x, ty = t1y;
        else
            tx = t2x, ty = t2y;
        double tn = sqrt(tx*tx + ty*ty);
        if (tn < 1e-12) break;
        tx /= tn; ty /= tn;
        double nx = x + step_size*tx;
        double ny = y + step_size*ty;
        // Project to contour
        for (int j = 0; j < 5; j++) {
            double hv = h_func(nx, ny);
            double gx2 = dh_dx(nx, ny);
            double gy2 = dh_dy(nx, ny);
            double g2 = gx2*gx2 + gy2*gy2;
            if (g2 < 1e-20) break;
            double corr = (hv - f) / g2;
            nx -= corr * gx2;
            ny -= corr * gy2;
        }
        total += sqrt((nx-x)*(nx-x) + (ny-y)*(ny-y));
        x = nx; y = ny;
        double d = sqrt((x-x1)*(x-x1) + (y-y1)*(y-y1));
        if (d < step_size * 2) {
            total += d;
            break;
        }
    }
    return total;
}

int main() {
    // Find f_min: max of h(x,0)
    double best_x = 895, best_h = h_func(895, 0);
    for (double x = 890; x <= 900; x += 0.001) {
        double hv = h_func(x, 0);
        if (hv > best_h) { best_h = hv; best_x = x; }
    }
    double f_min = best_h;
    double pinch_x = best_x;
    fprintf(stderr, "f_min = %.6f at x = %.6f\n", f_min, pinch_x);

    // Find tangent PA from A(200,200) on left branch
    // Binary search on y where tangent residual changes sign
    auto tangent_res_A = [&](double y) {
        double xl = find_contour_x(y, f_min, true);
        if (xl < 0) return 1e10;
        double gx = dh_dx(xl, y);
        double gy = dh_dy(xl, y);
        return gx*(xl-200) + gy*(y-200);
    };

    double lo = 40, hi = 50;
    for (int i = 0; i < 60; i++) {
        double mid = (lo+hi)/2;
        if (tangent_res_A(mid) < 0) lo = mid; else hi = mid;
    }
    double y_PA = (lo+hi)/2;
    double x_PA = find_contour_x(y_PA, f_min, true);
    fprintf(stderr, "PA = (%.6f, %.6f)\n", x_PA, y_PA);

    // Find tangent Q from B(1400,1400) on right branch
    auto tangent_res_B = [&](double y) {
        double xr = find_contour_x(y, f_min, false);
        if (xr < 0) return 1e10;
        double gx = dh_dx(xr, y);
        double gy = dh_dy(xr, y);
        return gx*(xr-1400) + gy*(y-1400);
    };

    lo = 870; hi = 875;
    for (int i = 0; i < 60; i++) {
        double mid = (lo+hi)/2;
        if (tangent_res_B(mid) < 0) lo = mid; else hi = mid;
    }
    double y_Q = (lo+hi)/2;
    double x_Q = find_contour_x(y_Q, f_min, false);
    fprintf(stderr, "Q = (%.6f, %.6f)\n", x_Q, y_Q);

    // Compute path
    double d_APA = sqrt((200-x_PA)*(200-x_PA) + (200-y_PA)*(200-y_PA));
    double arc1 = trace_arc(x_PA, y_PA, pinch_x, 0, f_min);
    double arc2 = trace_arc(pinch_x, 0, x_Q, y_Q, f_min);
    double d_QB = sqrt((x_Q-1400)*(x_Q-1400) + (y_Q-1400)*(y_Q-1400));

    double total = d_APA + arc1 + arc2 + d_QB;
    fprintf(stderr, "d(A,PA)=%.3f + arc1=%.3f + arc2=%.3f + d(Q,B)=%.3f = %.3f\n",
            d_APA, arc1, arc2, d_QB, total);
    printf("%.3f\n", total);
    return 0;
}

Python project_euler/problem_262/solution.py

"""
Problem 262: Mountain Range

h(x,y) = (5000 - 0.005*(x^2+y^2+x*y) + 12.5*(x+y))
         * exp(-abs(0.000001*(x^2+y^2) - 0.0015*(x+y) + 0.7))

A mosquito flies from A(200,200) to B(1400,1400) within 0<=x,y<=1600.
It ascends to elevation f, flies horizontally at f, then descends.

Find f_min (minimum elevation allowing such trip), then the shortest
horizontal path at f_min, rounded to 3 decimal places.

Solution approach:
1. f_min = minimax elevation = 10396.462193 (peak on y=0 boundary at x=895.483).
2. The barrier {h > f_min} is an annular (ring-shaped) region.
   It has a "pinch point" at (895.483, 0) where the barrier width is zero.
   By symmetry h(x,y)=h(y,x), another pinch exists at (0, 895.483).
3. The shortest path from A to B goes:
   A -> PA -> arc(PA, pinch) -> arc(pinch, Q) -> Q -> B
   where PA is tangent from A to the outer contour (left branch),
   and Q is tangent from B to the outer contour (right branch).
   The arc goes through the pinch point at (895.483, 0).
4. PA = (624.650, 48.254), Q = (1536.043, 873.038).
5. Path = 450.948 + 276.452 + 1259.565 + 544.239 = 2531.205.

Answer: 2531.205
"""

import math
from scipy.optimize import brentq, minimize_scalar

def h(x, y):
    t1 = x*x + y*y + x*y
    t2 = x*x + y*y
    base = 5000.0 - 0.005*t1 + 12.5*(x+y)
    ex = abs(0.000001*t2 - 0.0015*(x+y) + 0.7)
    return base * math.exp(-ex)

def dh_dx(x, y, eps=1e-7):
    return (h(x+eps, y) - h(x-eps, y)) / (2*eps)

def dh_dy(x, y, eps=1e-7):
    return (h(x, y+eps) - h(x, y-eps)) / (2*eps)

def outer_left_x(y, f_min):
    """First (leftmost) crossing of h=f_min at given y."""
    prev = h(0, y) - f_min
    for xi in range(1, 1601):
        cur = h(xi, y) - f_min
        if prev * cur < 0:
            return brentq(lambda x: h(x, y) - f_min, xi-1, xi)
        prev = cur
    return None

def outer_right_x(y, f_min):
    """Last (rightmost) crossing of h=f_min at given y."""
    prev = h(1600, y) - f_min
    for xi in range(1599, -1, -1):
        cur = h(xi, y) - f_min
        if prev * cur < 0:
            return brentq(lambda x: h(x, y) - f_min, xi, xi+1)
        prev = cur
    return None

def trace_arc(x0, y0, x1, y1, f_target, step=0.05, max_steps=200000):
    """Trace contour h=f_target from (x0,y0) toward (x1,y1), return arc length."""
    x, y = x0, y0
    total = 0.0
    for _ in range(max_steps):
        gx = dh_dx(x, y)
        gy = dh_dy(x, y)
        t1x, t1y = -gy, gx
        t2x, t2y = gy, -gx
        dx_t, dy_t = x1-x, y1-y
        if t1x*dx_t + t1y*dy_t > t2x*dx_t + t2y*dy_t:
            tx, ty = t1x, t1y
        else:
            tx, ty = t2x, t2y
        tn = math.sqrt(tx*tx + ty*ty)
        if tn < 1e-12: break
        tx /= tn; ty /= tn
        nx = x + step*tx
        ny = y + step*ty
        for _ in range(5):
            hv = h(nx, ny)
            gx2 = dh_dx(nx, ny)
            gy2 = dh_dy(nx, ny)
            g2 = gx2*gx2 + gy2*gy2
            if g2 < 1e-20: break
            corr = (hv - f_target) / g2
            nx -= corr * gx2
            ny -= corr * gy2
        total += math.sqrt((nx-x)**2 + (ny-y)**2)
        x, y = nx, ny
        if math.sqrt((x-x1)**2 + (y-y1)**2) < step * 2:
            total += math.sqrt((x-x1)**2 + (y-y1)**2)
            break
    return total

# Step 1: Find f_min (max of h on y=0 axis)
res = minimize_scalar(lambda x: -h(x, 0), bounds=(800, 1000), method='bounded')
f_min = -res.fun
pinch = (res.x, 0.0)
print(f"f_min = {f_min:.6f}")
print(f"Pinch point: ({pinch[0]:.3f}, {pinch[1]:.3f})")

# Step 2: Find tangent point PA from A(200,200) to left branch
def tangent_residual_A(y):
    xl = outer_left_x(y, f_min)
    if xl is None: return 1e10
    gx = dh_dx(xl, y)
    gy = dh_dy(xl, y)
    return gx*(xl-200) + gy*(y-200)

y_PA = brentq(tangent_residual_A, 40, 50)
x_PA = outer_left_x(y_PA, f_min)
PA = (x_PA, y_PA)
print(f"PA = ({PA[0]:.6f}, {PA[1]:.6f})")

# Step 3: Find tangent point Q from B(1400,1400) to right branch
def tangent_residual_B(y):
    xr = outer_right_x(y, f_min)
    if xr is None: return 1e10
    gx = dh_dx(xr, y)
    gy = dh_dy(xr, y)
    return gx*(xr-1400) + gy*(y-1400)

y_Q = brentq(tangent_residual_B, 870, 875)
x_Q = outer_right_x(y_Q, f_min)
Q = (x_Q, y_Q)
print(f"Q = ({Q[0]:.6f}, {Q[1]:.6f})")

# Step 4: Compute path lengths
d_APA = math.sqrt((200-PA[0])**2 + (200-PA[1])**2)
arc1 = trace_arc(PA[0], PA[1], pinch[0], pinch[1], f_min)
arc2 = trace_arc(pinch[0], pinch[1], Q[0], Q[1], f_min)
d_QB = math.sqrt((Q[0]-1400)**2 + (Q[1]-1400)**2)

total = d_APA + arc1 + arc2 + d_QB
print(f"\nPath breakdown:")
print(f"  d(A, PA) = {d_APA:.3f}")
print(f"  arc(PA, pinch) = {arc1:.3f}")
print(f"  arc(pinch, Q) = {arc2:.3f}")
print(f"  d(Q, B) = {d_QB:.3f}")
print(f"  Total = {total:.3f}")
print(f"\n{total:.3f}")