BOJ 1069 - Going Home

Problem link

Let $D_0=\sqrt{x^2+y^2}$ be the distance from the starting point to the target. Walking directly takes $D_0$ time. A jump always covers exactly $D$ distance, takes time $T$, and may be made in any direction; walking can cover any remaining distance.

Write $q=\lfloor D_0/D\rfloor$ and $r=D_0-qD$, so $0\le r<D$. The natural candidates are:

• Walk all the way: $D_0$.
• Make $q$ jumps toward the target, then walk the remaining $r$: $qT+r$.
• Make $q+1$ jumps in the target direction and walk back the overshoot $D-r$: $(q+1)T+D-r$.
• Reach the target using $q+1$ jumps: $(q+1)T$. For $q\ge1$, make $q-1$ jumps along the target direction, then use two jumps whose resultant displacement is $D+r$. Any resultant length from $0$ to $2D$ is possible with two length-$D$ jumps, and $D+r<2D$. For $q=0$, two jumps can directly have resultant length $D_0<D$, so the same time applies.

These candidates cover the optimum. With $n\le q$ jumps, the remaining distance cannot be less than $D_0-nD$, so that strategy costs at least $nT+D_0-nD$, a linear function of $n$ whose minimum on this range occurs at $n=0$ or $n=q$. With at least $q+1$ jumps, the jump cost alone is at least $(q+1)T$, and that cost is achievable as described above. This also handles $q=0$; for one jump, the best remaining distance is $|D-D_0|=D-r$, and two jumps can reach the target. Thus the minimum of the listed candidates is valid, including when $D_0<D$ or $r=0$.

C++17 implementation

hypot computes the Euclidean distance robustly. The running time and extra space are both $O(1)$.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

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

    double x, y, jumpDistance, jumpTime;
    std::cin >> x >> y >> jumpDistance >> jumpTime;

    const double distance = std::hypot(x, y);
    const auto q = static_cast<long long>(std::floor(distance / jumpDistance));
    const double remainder = distance - q * jumpDistance;

    double answer = distance;
    if (q == 0) {
        answer = std::min({answer,
                           jumpTime + jumpDistance - distance,
                           2.0 * jumpTime});
    } else {
        answer = std::min({answer,
                           q * jumpTime + remainder,
                           (q + 1) * jumpTime + jumpDistance - remainder,
                           (q + 1) * jumpTime});
    }

    std::cout << std::fixed << std::setprecision(10) << answer << '\n';
    return 0;
}