Overview

This problem asks us to find the minimum number of jumps required to travel from the mothership at \((0, 0)\) to the space station at \((0, W)\), passing through at least one piece of debris, such that each jump covers a distance of at most \(D\). By combining Breadth-First Search (BFS) with a kd-tree, we can find the shortest path efficiently.

Analysis

Formulation as a Shortest Path Problem on a Graph

Consider an undirected graph where the mothership, each piece of debris, and the space station are vertices, and an edge exists between any two vertices with a distance of at most \(D\). Then, the minimum number of jumps from the mothership to the space station can be found via Breadth-First Search (BFS) as an unweighted shortest path problem.

Issues with the Naive Approach

The number of debris is \(N \le 10^5\). If we try to compute distances between all pairs of debris to construct edges, it would take \(O(N^2)\) time and space, resulting in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE).

Solution

An essential property of BFS is that each vertex is pushed to the queue (visited) at most once. Therefore, there is no need to explicitly store all edges of the graph beforehand. It is sufficient if we can perform the following operation quickly at each step of the BFS:

• Query: Enumerate all unvisited debris inside the circle of radius \(D\) centered at point \((x, y)\), and mark them as visited.

To handle such geometric range queries on a set of 2D points, using a kd-tree is very effective.

Algorithm

1. Constructing the kd-tree

   • Build a balanced binary search tree, a kd-tree, from the coordinates of the \(N\) pieces of debris.
   • Depending on the depth of the tree, alternate between splitting the region in half by the median of the \(x\)-coordinates and the \(y\)-coordinates.
   • Each node maintains the bounding box (minimum bounding rectangle: \([min\_x, max\_x] \times [min\_y, max\_y]\)) of all points in its subtree, as well as a flag has_unvisited indicating whether there are unvisited vertices in the subtree.

2. Pruning Range Queries (Circle and Rectangle Intersection)

   • When traversing a node’s subtree for a query circle centered at \((cx, cy)\) with radius \(D\), perform the following checks:
     1. No search needed (Skip): If all points in the subtree are already visited (!has_unvisited).
     2. Outside the circle (Skip): If the minimum distance between the bounding box and the center \((cx, cy)\) is greater than \(D\), prune the search since no points in this subtree lie inside the circle.
     3. Fully contained inside the circle (Collect all): If the maximum distance between the bounding box and the center \((cx, cy)\) is at most \(D\), all points in the rectangle are inside the circle. Collect all unvisited points in this subtree at once.
     4. Partially overlapping: If the point of the current node is inside the circle and unvisited, collect it, and recursively search both the left and right children.
   • After the traversal, if no unvisited points remain in the subtree, update has_unvisited = false.

3. BFS (Breadth-First Search)

   • Search for debris within distance \(D\) from the mothership \((0, 0)\) using the kd-tree, and push them into the queue with a distance of \(1\).
   • Pop debris from the queue and perform the following:
     • If the distance from this debris to the space station \((0, W)\) is at most \(D\), reaching the destination is possible; output current jumps + 1 and terminate.
     • Using the kd-tree, retrieve all unvisited debris within distance \(D\) from this debris, update their distances, and push them to the queue.
   • If the queue becomes empty without reaching the space station, output -1.

Complexity

• Time Complexity:
  • kd-tree construction: \(O(N \log N)\) using std::nth_element.
  • BFS traversal: Each vertex is visited (collected) at most once, and visited subtrees are pruned by the has_unvisited flag, so it operates very fast overall (on average around \(O(N \log N)\) or \(O(N \sqrt{N})\)). It easily passes within the time limit for \(N = 10^5\).
• Space Complexity: \(O(N)\)
  • The number of nodes in the kd-tree, the queue for BFS, and the distance array are all \(O(N)\).

Implementation Details

• Preventing Overflow:

  • The coordinates and the jump distance \(D\) can be up to \(10^9\). When calculating the squared distance, the difference along an axis can be up to \(2 \times 10^9\), and the sum of squared differences can reach approximately \(8 \times 10^{18}\). Since this is close to the maximum value of a standard 64-bit signed integer (long long, \(\approx 9.22 \times 10^{18}\)), using a 128-bit integer type (__int128_t) for computing squared distances safely prevents any potential overflow.

• Optimization on Full Containment (collect_all):

  • When a bounding box is completely contained within the circle, skipping the distance calculations for individual points inside the rectangle and collecting them all at once avoids redundant distance checks, significantly speeding up the execution.

    Source Code

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

struct Point {
    long long x, y;
    int id;
};

struct Node {
    int pt_idx;
    long long x, y;
    int left = -1, right = -1;
    long long min_x, max_x, min_y, max_y;
    bool has_unvisited = true;
};

vector<Node> nodes;
vector<Point> pts;
vector<bool> visited;

int build(int l, int r, int depth) {
    if (l >= r) return -1;
    int mid = l + (r - l) / 2;
    int axis = depth % 2;
    if (axis == 0) {
        nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r,
            [](const Point& a, const Point& b) {
                return a.x < b.x;
            });
    } else {
        nth_element(pts.begin() + l, pts.begin() + mid, pts.begin() + r,
            [](const Point& a, const Point& b) {
                return a.y < b.y;
            });
    }

    int u = nodes.size();
    nodes.emplace_back();
    nodes[u].pt_idx = pts[mid].id;
    nodes[u].x = pts[mid].x;
    nodes[u].y = pts[mid].y;
    nodes[u].min_x = nodes[u].max_x = pts[mid].x;
    nodes[u].min_y = nodes[u].max_y = pts[mid].y;

    int left_child = build(l, mid, depth + 1);
    int right_child = build(mid + 1, r, depth + 1);

    nodes[u].left = left_child;
    nodes[u].right = right_child;

    if (left_child != -1) {
        nodes[u].min_x = min(nodes[u].min_x, nodes[left_child].min_x);
        nodes[u].max_x = max(nodes[u].max_x, nodes[left_child].max_x);
        nodes[u].min_y = min(nodes[u].min_y, nodes[left_child].min_y);
        nodes[u].max_y = max(nodes[u].max_y, nodes[left_child].max_y);
    }
    if (right_child != -1) {
        nodes[u].min_x = min(nodes[u].min_x, nodes[right_child].min_x);
        nodes[u].max_x = max(nodes[u].max_x, nodes[right_child].max_x);
        nodes[u].min_y = min(nodes[u].min_y, nodes[right_child].min_y);
        nodes[u].max_y = max(nodes[u].max_y, nodes[right_child].max_y);
    }

    return u;
}

void collect_all(int u, vector<int>& found) {
    if (u == -1 || !nodes[u].has_unvisited) return;
    if (!visited[nodes[u].pt_idx]) {
        visited[nodes[u].pt_idx] = true;
        found.push_back(nodes[u].pt_idx);
    }
    collect_all(nodes[u].left, found);
    collect_all(nodes[u].right, found);
    nodes[u].has_unvisited = false;
}

void query(int u, long long cx, long long cy, long long D, vector<int>& found) {
    if (u == -1 || !nodes[u].has_unvisited) return;

    long long dx = 0;
    if (cx < nodes[u].min_x) dx = nodes[u].min_x - cx;
    else if (cx > nodes[u].max_x) dx = cx - nodes[u].max_x;

    long long dy = 0;
    if (cy < nodes[u].min_y) dy = nodes[u].min_y - cy;
    else if (cy > nodes[u].max_y) dy = cy - nodes[u].max_y;

    if ((__int128_t)dx * dx + (__int128_t)dy * dy > (__int128_t)D * D) {
        return;
    }

    long long max_dx = max(abs(cx - nodes[u].min_x), abs(cx - nodes[u].max_x));
    long long max_dy = max(abs(cy - nodes[u].min_y), abs(cy - nodes[u].max_y));

    if ((__int128_t)max_dx * max_dx + (__int128_t)max_dy * max_dy <= (__int128_t)D * D) {
        collect_all(u, found);
        return;
    }

    if (!visited[nodes[u].pt_idx]) {
        long long dpx = cx - nodes[u].x;
        long long dpy = cy - nodes[u].y;
        if ((__int128_t)dpx * dpx + (__int128_t)dpy * dpy <= (__int128_t)D * D) {
            visited[nodes[u].pt_idx] = true;
            found.push_back(nodes[u].pt_idx);
        }
    }

    query(nodes[u].left, cx, cy, D, found);
    query(nodes[u].right, cx, cy, D, found);

    nodes[u].has_unvisited = !visited[nodes[u].pt_idx] ||
        (nodes[u].left != -1 && nodes[nodes[u].left].has_unvisited) ||
        (nodes[u].right != -1 && nodes[nodes[u].right].has_unvisited);
}

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

    int N;
    long long W, D;
    if (!(cin >> N >> W >> D)) return 0;

    pts.resize(N);
    vector<long long> orig_x(N), orig_y(N);
    for (int i = 0; i < N; ++i) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i;
        orig_x[i] = pts[i].x;
        orig_y[i] = pts[i].y;
    }

    nodes.reserve(N);
    visited.assign(N, false);
    int root = build(0, N, 0);

    queue<int> q;
    vector<int> dist(N, -1);

    vector<int> initial;
    query(root, 0, 0, D, initial);
    for (int id : initial) {
        dist[id] = 1;
        q.push(id);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        long long to_target_x = 0 - orig_x[u];
        long long to_target_y = W - orig_y[u];
        if ((__int128_t)to_target_x * to_target_x + (__int128_t)to_target_y * to_target_y <= (__int128_t)D * D) {
            cout << dist[u] + 1 << "\n";
            return 0;
        }

        vector<int> nxt;
        query(root, orig_x[u], orig_y[u], D, nxt);
        for (int v : nxt) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }

    cout << -1 << "\n";
    return 0;
}

This editorial was generated by gemini-3.8-flash-high.