ICPC 2023 - D. Carl’s Vacation

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

namespace {

using ld = long double;

struct Point {
    ld x = 0;
    ld y = 0;

    Point operator+(const Point& other) const {
        return {x + other.x, y + other.y};
    }
    Point operator-(const Point& other) const {
        return {x - other.x, y - other.y};
    }
    Point operator*(ld scale) const {
        return {x * scale, y * scale};
    }
};

ld dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

ld norm(const Point& a) {
    return sqrtl(dot(a, a));
}

Point left_normal(const Point& v) {
    return {-v.y, v.x};
}

struct Pyramid {
    array<Point, 4> base;
    Point center;
    ld height = 0;
};

Pyramid read_pyramid() {
    long long x1, y1, x2, y2, h;
    cin >> x1 >> y1 >> x2 >> y2 >> h;

    Point a{static_cast<ld>(x1), static_cast<ld>(y1)};
    Point b{static_cast<ld>(x2), static_cast<ld>(y2)};
    Point edge = b - a;
    ld side = norm(edge);
    Point inside = left_normal(edge) * (1.0L / side);

    Pyramid pyramid;
    pyramid.base[0] = a;
    pyramid.base[1] = b;
    pyramid.base[2] = b + inside * side;
    pyramid.base[3] = a + inside * side;
    pyramid.center = (pyramid.base[0] + pyramid.base[2]) * 0.5L;
    pyramid.height = h;
    return pyramid;
}

void solve() {
    Pyramid first = read_pyramid();
    Pyramid second = read_pyramid();

    auto point_on_edge = [](const Point& a, const Point& b, ld t) {
        return a + (b - a) * t;
    };

    auto distance_to_apex = [](const Point& center, ld height, const Point& p) {
        Point diff = p - center;
        return sqrtl(dot(diff, diff) + height * height);
    };

    ld answer = 1e100L;
    for (int i = 0; i < 4; ++i) {
        Point e1 = first.base[i];
        Point e2 = first.base[(i + 1) % 4];
        for (int j = 0; j < 4; ++j) {
            Point f1 = second.base[j];
            Point f2 = second.base[(j + 1) % 4];

            auto value = [&](ld x, ld y) {
                Point p = point_on_edge(e1, e2, x);
                Point q = point_on_edge(f1, f2, y);
                return distance_to_apex(first.center, first.height, p) +
                       norm(p - q) +
                       distance_to_apex(second.center, second.height, q);
            };

            auto best_for_x = [&](ld x) {
                ld low = 0;
                ld high = 1;
                for (int it = 0; it < 80; ++it) {
                    ld m1 = (2 * low + high) / 3;
                    ld m2 = (low + 2 * high) / 3;
                    if (value(x, m1) < value(x, m2)) {
                        high = m2;
                    } else {
                        low = m1;
                    }
                }
                return value(x, (low + high) * 0.5L);
            };

            ld low = 0;
            ld high = 1;
            for (int it = 0; it < 80; ++it) {
                ld m1 = (2 * low + high) / 3;
                ld m2 = (low + 2 * high) / 3;
                if (best_for_x(m1) < best_for_x(m2)) {
                    high = m2;
                } else {
                    low = m1;
                }
            }
            answer = min(answer, best_for_x((low + high) * 0.5L));
        }
    }

    cout << fixed << setprecision(9) << static_cast<double>(answer) << '\n';
}

}  // namespace

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

    solve();
    return 0;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2023\\D. Carl's Vacation}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

We must find the shortest path from the apex of one right square pyramid to the apex of another, where
the ant may walk only on the pyramid surfaces and on the ground plane.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item Once we choose one side face on each pyramid, the path has three pieces: a segment on the first
    triangular face from the first apex to some point on that face's base edge, a straight ground segment,
    and a segment on the second triangular face to the second apex.
    \item There are only $4 \cdot 4 = 16$ choices of side faces.
    \item If $p$ and $q$ are the two ground contact points, then the total length is
    \[
    \sqrt{\|p-c_1\|^2+h_1^2}+\|p-q\|+\sqrt{\|q-c_2\|^2+h_2^2},
    \]
    where $c_i$ is the center of the $i$th base and $h_i$ its height.
    \item Parameterizing $p$ and $q$ along their chosen edges gives a convex function on
    $[0,1]\times[0,1]$, so nested ternary search finds the minimum for that edge pair.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Reconstruct the four base corners of each pyramid from the given directed edge. The remaining
    two corners are obtained by moving along a left normal of the edge.
    \item For every edge $e$ of the first base and every edge $f$ of the second base:
    \begin{itemize}[leftmargin=*]
        \item let $p(x)$ be the point at parameter $x \in [0,1]$ on $e$;
        \item let $q(y)$ be the point at parameter $y \in [0,1]$ on $f$;
        \item define
        \[
        L(x,y)=\sqrt{\|p(x)-c_1\|^2+h_1^2}+\|p(x)-q(y)\|+\sqrt{\|q(y)-c_2\|^2+h_2^2}.
        \]
    \end{itemize}
    \item For fixed $x$, minimize $L(x,y)$ over $y$ by ternary search.
    \item Minimize the resulting one-variable function over $x$ by another ternary search.
    \item Take the minimum over all $16$ edge pairs.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
For a fixed triangular side face and a fixed point on its base edge, the shortest path from the apex to
that point is the straight segment inside the triangle.

\paragraph{Proof.}
The face is a planar triangle, hence convex. In a plane, the shortest path between two points is their
Euclidean segment, and that segment stays inside the triangle. \qed

\paragraph{Lemma 2.}
For some optimal route, the path uses exactly one side face of each pyramid and one ground segment, as
enumerated by the algorithm.

\paragraph{Proof.}
Any valid route must leave each pyramid through some point of its square base boundary and then travel
across the ground plane. Fix those two boundary points. By Lemma 1, the best way to connect an apex to
its chosen boundary point is a straight segment within one incident triangular face. The best ground-plane
path between the two boundary points is the straight segment joining them. Therefore some optimal route
has exactly the form considered by the algorithm. \qed

\paragraph{Lemma 3.}
For a fixed pair of base edges, the function $L(x,y)$ is convex on $[0,1]\times[0,1]$.

\paragraph{Proof.}
The maps $x \mapsto p(x)$ and $y \mapsto q(y)$ are affine. The Euclidean norm is convex, so each term
\[
\sqrt{\|p(x)-c_1\|^2+h_1^2},\quad \|p(x)-q(y)\|,\quad \sqrt{\|q(y)-c_2\|^2+h_2^2}
\]
is convex in its arguments, and their sum is convex as well. Hence every one-dimensional restriction used
by the nested ternary searches is unimodal. \qed

\paragraph{Theorem.}
The algorithm outputs the minimum possible travel distance.

\paragraph{Proof.}
By Lemma 2, some optimal route is represented by one of the $16$ edge pairs checked by the algorithm.
For that pair, Lemma 3 implies that nested ternary search finds the global minimum of $L(x,y)$. Taking
the minimum over all edge pairs therefore yields the true optimum. \qed

\section*{Complexity Analysis}

The algorithm checks $16$ edge pairs, and for each it performs a constant number of ternary-search
iterations. Therefore the running time is $O(1)$ and the memory usage is $O(1)$.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item The implementation performs $80$ iterations in each ternary search, which is ample for the
    required error bound.
    \item All geometry is done in \texttt{long double}.
\end{itemize}

\end{document}