Overview

We model the debris as vertices and add an edge between two pieces of debris if the distance between them is at most \(D\). The goal is to find the minimum number of jumps from the mothership to the space station.

Checking the distance between all pairs of debris takes \(O(N^2)\) time, which is too slow to pass within the time limit. Therefore, we divide the plane into small cells and perform a BFS, inspecting only the nearby cells that could potentially be within distance \(D\).

Analysis

Since each jump has a cost of \(1\), the problem reduces to finding the “shortest path length”.
Thus, we can find the minimum number of jumps using BFS.

However, if we naively:

• check the distance between every pair of debris, and
• construct all edges to run BFS,

there can be up to \(O(N^2)\) candidate edges.
Since \(N \leq 10^5\), this approach will not finish in time.

To resolve this, we leverage the following properties:

• From any given point, we can only transition to points within distance \(D\).
• Points located in distant regions can never be reached in the next step.

We partition the plane into square cells of side length \(S\).
In this implementation, we set:

\[ S = \left\lfloor \frac{D}{3} \right\rfloor + 1 \]

With this choice, the number of cells that can be within distance \(D\) from any given cell is bounded by a constant.
Indeed, since \(S > D/3\), cells with large coordinate differences are guaranteed to be strictly farther than distance \(D\).

Furthermore, we make the following checks between pairs of cells:

• If the distance between any point in one cell and any point in the other is at most \(D\), all unvisited points in that cell can be visited at once.
• If the distance between any point in one cell and any point in the other is strictly greater than \(D\), that cell can be ignored.
• Only in the remaining cases do we check distances between individual points.

This avoids checking all pairs of points.

Algorithm

1. Assigning Debris to Cells

For each debris \((x_i, y_i)\), we calculate its cell coordinates as:

\[ g_x = \left\lfloor \frac{x_i}{S} \right\rfloor,\quad g_y = \left\lfloor \frac{y_i}{S} \right\rfloor \]

For each cell, we track:

• The indices of debris it contains
• The number of unvisited debris
• The minimum and maximum \(x\)- and \(y\)-coordinates among the debris in the cell

Because the cell coordinates can become very large, we store them in an unordered_map rather than a 2D array.

2. Precomputing Relative Cell Offsets to Check

From a reference cell, we precompute whether a cell at relative offset \((dx, dy)\) can possibly be within distance \(D\).

If the minimum distance between the two cells is strictly greater than \(D\), we can ignore that relative offset.

Conversely, if the maximum distance between the two cells is at most \(D\), that relative offset is considered “fully reachable”.
In this case, all unvisited points in the target cell can be added to the next BFS layer without checking individual distances.

3. Performing the BFS

Let cur be the current BFS layer and nxt be the next layer.

We begin at the mothership’s position \((0,0)\).
However, jumping directly from the mothership to the space station is prohibited, so we do not perform a goal check at depth \(0\).

The procedure for each BFS layer is as follows:

1. If any debris in the current layer is within distance \(D\) of the space station \((0,W)\), the answer is current depth + 1.
2. Group the debris in the current layer by cell.
3. For each cell group, inspect only the potentially reachable neighboring cells.
4. If a target cell contains unvisited debris, add all reachable debris to nxt.

4. Cell-level Optimization

Let source be a set of points in the current layer, and target be the candidate cell to inspect.

First, consider the bounding rectangles of both point sets:

• If the minimum distance between the two rectangles is strictly greater than \(D\):
  \(\to\) It is impossible to reach, so ignore it.
• If the maximum distance between the two rectangles is at most \(D\):
  \(\to\) All points are reachable, so visit the entire target cell at once.
• Otherwise:
  \(\to\) For each point, check whether there exists a point in source within distance \(D\).

To perform this existence query efficiently, we use a KD-tree.

In the KD-tree, each subtree maintains the bounding box of the points it contains.
If the minimum distance from the query point to this bounding box is strictly greater than \(D\), we can prune that entire subtree.

5. Correctness

In BFS, the points in the current layer are precisely those whose “minimum number of jumps equals the current depth”.

In this implementation, all unvisited debris reachable within distance \(D\) from any point in the current layer are added to the next layer:

• When an entire cell is added at once, we have verified that the maximum pairwise distance between the sets is at most \(D\).
• When points are added individually, the KD-tree confirms that a point in source within distance \(D\) actually exists.

Therefore, invalid points are never added.

Moreover, if any point within distance \(D\) exists, its cell is guaranteed to be among the precomputed candidate offsets, so no points are missed.

By the properties of BFS, the first time the space station is reached corresponds to the minimum number of jumps.

Complexity

• Time Complexity: Expected \(O(N \log N)\)
• Space Complexity: \(O(N)\)

This assumes hash table operations take expected \(O(1)\) time and KD-tree queries take \(O(\log N)\) on average.

Additionally, the number of relative cells examined from each cell is bounded by a constant.
Because points within the same cell are at distance at most \(D\) from each other, the number of times any cell can appear as a BFS source is also bounded by a constant.

Implementation Notes

• Avoid using floating-point square roots when comparing distances; compare squared distances instead: $\( (x_1-x_2)^2 + (y_1-y_2)^2 \leq D^2 \)$

• Coordinates and squared distances can become very large, so __int128 is used.

• Since \(x_i\) can be negative, calculating cell coordinates requires mathematical floor division rather than standard C++ integer division (which truncates towards zero).

• Directly jumping from the mothership to the space station is forbidden, so do not check for reaching the goal at depth \(0\).

• Use a custom hash function for unordered_map to avoid performance drops caused by hash collisions.

  Source Code

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

using ll = long long;

struct Point {
    ll x, y;
    int cell;
};

struct Key {
    ll x, y;
    bool operator==(const Key& other) const {
        return x == other.x && y == other.y;
    }
};

struct KeyHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(const Key& k) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        uint64_t h1 = splitmix64((uint64_t)k.x + FIXED_RANDOM);
        uint64_t h2 = splitmix64((uint64_t)k.y + FIXED_RANDOM + 0x9e3779b97f4a7c15ULL);
        return (size_t)(h1 ^ (h2 << 1));
    }
};

struct Cell {
    ll gx, gy;
    vector<int> pts;
    int rem = 0;
    ll minx, maxx, miny, maxy;
};

struct Offset {
    ll dx, dy;
    bool complete;
    __int128 minSq;
};

int N;
ll W, D, S;
__int128 D2;

vector<Point> P;
vector<Cell> cells;
vector<int> distv;
vector<Offset> offsets;
unordered_map<Key, int, KeyHash> mp;

inline __int128 sq128(__int128 x) {
    return x * x;
}

inline __int128 dist2_points(ll ax, ll ay, ll bx, ll by) {
    return sq128((__int128)ax - bx) + sq128((__int128)ay - by);
}

ll floor_div(ll a, ll b) {
    if (a >= 0) return a / b;
    return - ((-a + b - 1) / b);
}

__int128 minDistRect(ll aminx, ll amaxx, ll aminy, ll amaxy,
                     ll bminx, ll bmaxx, ll bminy, ll bmaxy) {
    __int128 dx = 0, dy = 0;
    if (amaxx < bminx) dx = (__int128)bminx - amaxx;
    else if (bmaxx < aminx) dx = (__int128)aminx - bmaxx;

    if (amaxy < bminy) dy = (__int128)bminy - amaxy;
    else if (bmaxy < aminy) dy = (__int128)aminy - bmaxy;

    return dx * dx + dy * dy;
}

__int128 maxDistRect(ll aminx, ll amaxx, ll aminy, ll amaxy,
                     ll bminx, ll bmaxx, ll bminy, ll bmaxy) {
    __int128 dx1 = (__int128)aminx - bmaxx;
    if (dx1 < 0) dx1 = -dx1;
    __int128 dx2 = (__int128)amaxx - bminx;
    if (dx2 < 0) dx2 = -dx2;
    __int128 dx = max(dx1, dx2);

    __int128 dy1 = (__int128)aminy - bmaxy;
    if (dy1 < 0) dy1 = -dy1;
    __int128 dy2 = (__int128)amaxy - bminy;
    if (dy2 < 0) dy2 = -dy2;
    __int128 dy = max(dy1, dy2);

    return dx * dx + dy * dy;
}

__int128 minDistPointRect(ll x, ll y, ll minx, ll maxx, ll miny, ll maxy) {
    __int128 dx = 0, dy = 0;
    if (x < minx) dx = (__int128)minx - x;
    else if (x > maxx) dx = (__int128)x - maxx;

    if (y < miny) dy = (__int128)miny - y;
    else if (y > maxy) dy = (__int128)y - maxy;

    return dx * dx + dy * dy;
}

__int128 maxDistPointRect(ll x, ll y, ll minx, ll maxx, ll miny, ll maxy) {
    __int128 dx1 = (__int128)x - minx;
    if (dx1 < 0) dx1 = -dx1;
    __int128 dx2 = (__int128)x - maxx;
    if (dx2 < 0) dx2 = -dx2;
    __int128 dx = max(dx1, dx2);

    __int128 dy1 = (__int128)y - miny;
    if (dy1 < 0) dy1 = -dy1;
    __int128 dy2 = (__int128)y - maxy;
    if (dy2 < 0) dy2 = -dy2;
    __int128 dy = max(dy1, dy2);

    return dx * dx + dy * dy;
}

struct KDTree {
    struct Node {
        ll x, y;
        ll minx, maxx, miny, maxy;
        int l = -1, r = -1;
    };

    vector<Node> nodes;
    vector<pair<ll, ll>> arr;
    int root = -1;

    int build_rec(int l, int r, int depth) {
        if (l >= r) return -1;

        int m = (l + r) >> 1;
        int axis = depth & 1;

        nth_element(arr.begin() + l, arr.begin() + m, arr.begin() + r,
                    [axis](const auto& a, const auto& b) {
                        return axis == 0 ? a.first < b.first : a.second < b.second;
                    });

        int idx = (int)nodes.size();
        nodes.push_back(Node{arr[m].first, arr[m].second,
                             arr[m].first, arr[m].first,
                             arr[m].second, arr[m].second,
                             -1, -1});

        int lc = build_rec(l, m, depth + 1);
        int rc = build_rec(m + 1, r, depth + 1);

        nodes[idx].l = lc;
        nodes[idx].r = rc;

        auto pull = [&](int c) {
            if (c == -1) return;
            nodes[idx].minx = min(nodes[idx].minx, nodes[c].minx);
            nodes[idx].maxx = max(nodes[idx].maxx, nodes[c].maxx);
            nodes[idx].miny = min(nodes[idx].miny, nodes[c].miny);
            nodes[idx].maxy = max(nodes[idx].maxy, nodes[c].maxy);
        };
        pull(lc);
        pull(rc);

        return idx;
    }

    void buildFrom(vector<pair<ll, ll>>&& v) {
        arr = move(v);
        nodes.reserve(arr.size());
        root = build_rec(0, (int)arr.size(), 0);
    }

    __int128 minDistNode(int idx, ll qx, ll qy) const {
        const Node& n = nodes[idx];
        return minDistPointRect(qx, qy, n.minx, n.maxx, n.miny, n.maxy);
    }

    bool query_rec(int idx, ll qx, ll qy) const {
        if (idx == -1) return false;
        if (minDistNode(idx, qx, qy) > D2) return false;

        const Node& n = nodes[idx];

        if (dist2_points(n.x, n.y, qx, qy) <= D2) return true;

        int lc = n.l, rc = n.r;
        __int128 dl = (lc == -1 ? D2 + 1 : minDistNode(lc, qx, qy));
        __int128 dr = (rc == -1 ? D2 + 1 : minDistNode(rc, qx, qy));

        if (dl > dr) {
            swap(dl, dr);
            swap(lc, rc);
        }

        if (dl <= D2 && query_rec(lc, qx, qy)) return true;
        if (dr <= D2 && query_rec(rc, qx, qy)) return true;

        return false;
    }

    bool query(ll qx, ll qy) const {
        if (root == -1) return false;
        return query_rec(root, qx, qy);
    }
};

struct Source {
    const vector<int>* ids;
    int l, r;
    ll gx, gy;
    ll minx, maxx, miny, maxy;

    mutable bool built = false;
    mutable KDTree kd;

    Source(const vector<int>& v, int L, int R, ll GX, ll GY)
        : ids(&v), l(L), r(R), gx(GX), gy(GY) {
        const ll INF = (1LL << 62);
        minx = miny = INF;
        maxx = maxy = -INF;

        for (int i = l; i < r; i++) {
            int id = (*ids)[i];
            ll x, y;
            if (id == -1) {
                x = 0;
                y = 0;
            } else {
                x = P[id].x;
                y = P[id].y;
            }
            minx = min(minx, x);
            maxx = max(maxx, x);
            miny = min(miny, y);
            maxy = max(maxy, y);
        }
    }

    int size() const {
        return r - l;
    }

    void buildKD() const {
        if (built) return;

        vector<pair<ll, ll>> v;
        v.reserve(size());

        for (int i = l; i < r; i++) {
            int id = (*ids)[i];
            if (id == -1) v.push_back({0, 0});
            else v.push_back({P[id].x, P[id].y});
        }

        kd.buildFrom(move(v));
        built = true;
    }

    bool existsWithin(ll qx, ll qy) const {
        if (minDistPointRect(qx, qy, minx, maxx, miny, maxy) > D2) return false;
        if (maxDistPointRect(qx, qy, minx, maxx, miny, maxy) <= D2) return true;

        if (size() <= 16) {
            for (int i = l; i < r; i++) {
                int id = (*ids)[i];
                ll x, y;
                if (id == -1) {
                    x = 0;
                    y = 0;
                } else {
                    x = P[id].x;
                    y = P[id].y;
                }
                if (dist2_points(x, y, qx, qy) <= D2) return true;
            }
            return false;
        }

        buildKD();
        return kd.query(qx, qy);
    }
};

void add_point(int id, int nd, vector<int>& nxt) {
    distv[id] = nd;
    nxt.push_back(id);
    cells[P[id].cell].rem--;
}

void visit_all(int cid, int nd, vector<int>& nxt) {
    Cell& c = cells[cid];
    if (c.rem == 0) return;

    for (int id : c.pts) {
        if (distv[id] == -1) {
            add_point(id, nd, nxt);
        }
    }
    c.rem = 0;
}

void process_group(const Source& src, int depth, vector<int>& nxt) {
    int nd = depth + 1;

    for (const auto& off : offsets) {
        Key key{src.gx + off.dx, src.gy + off.dy};
        auto it = mp.find(key);
        if (it == mp.end()) continue;

        int cid = it->second;
        Cell& tc = cells[cid];

        if (tc.rem == 0) continue;

        if (off.complete ||
            maxDistRect(src.minx, src.maxx, src.miny, src.maxy,
                        tc.minx, tc.maxx, tc.miny, tc.maxy) <= D2) {
            visit_all(cid, nd, nxt);
            continue;
        }

        if (minDistRect(src.minx, src.maxx, src.miny, src.maxy,
                        tc.minx, tc.maxx, tc.miny, tc.maxy) > D2) {
            continue;
        }

        for (int id : tc.pts) {
            if (tc.rem == 0) break;
            if (distv[id] != -1) continue;

            if (src.existsWithin(P[id].x, P[id].y)) {
                add_point(id, nd, nxt);
            }
        }
    }
}

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

    cin >> N >> W >> D;

    D2 = (__int128)D * D;
    S = D / 3 + 1;

    P.resize(N);
    distv.assign(N, -1);

    mp.reserve(N * 2 + 10);
    mp.max_load_factor(0.7);

    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;

        P[i].x = x;
        P[i].y = y;

        ll gx = floor_div(x, S);
        ll gy = floor_div(y, S);
        Key key{gx, gy};

        auto it = mp.find(key);
        int cid;

        if (it == mp.end()) {
            cid = (int)cells.size();
            mp.emplace(key, cid);

            Cell c;
            c.gx = gx;
            c.gy = gy;
            c.minx = c.maxx = x;
            c.miny = c.maxy = y;
            cells.push_back(move(c));
        } else {
            cid = it->second;
        }

        P[i].cell = cid;

        Cell& c = cells[cid];
        c.pts.push_back(i);
        c.rem++;
        c.minx = min(c.minx, x);
        c.maxx = max(c.maxx, x);
        c.miny = min(c.miny, y);
        c.maxy = max(c.maxy, y);
    }

    ll R = D / S + 2;

    for (ll dx = -R; dx <= R; dx++) {
        for (ll dy = -R; dy <= R; dy++) {
            ll adx = llabs(dx);
            ll ady = llabs(dy);

            __int128 minx = (adx == 0 ? 0 : (__int128)(adx - 1) * S + 1);
            __int128 miny = (ady == 0 ? 0 : (__int128)(ady - 1) * S + 1);
            __int128 minSq = minx * minx + miny * miny;

            if (minSq > D2) continue;

            __int128 maxx = (__int128)(adx + 1) * S - 1;
            __int128 maxy = (__int128)(ady + 1) * S - 1;
            __int128 maxSq = maxx * maxx + maxy * maxy;

            offsets.push_back(Offset{dx, dy, maxSq <= D2, minSq});
        }
    }

    sort(offsets.begin(), offsets.end(), [](const Offset& a, const Offset& b) {
        if (a.complete != b.complete) return a.complete > b.complete;
        return a.minSq < b.minSq;
    });

    vector<int> cur, nxt;
    cur.reserve(N);
    nxt.reserve(N);

    cur.push_back(-1);

    int depth = 0;

    while (!cur.empty()) {
        if (depth > 0) {
            for (int id : cur) {
                if (dist2_points(P[id].x, P[id].y, 0, W) <= D2) {
                    cout << depth + 1 << '\n';
                    return 0;
                }
            }
        }

        nxt.clear();

        if (depth == 0) {
            vector<int> start_vec = {-1};
            Source src(start_vec, 0, 1, 0, 0);
            process_group(src, depth, nxt);
        } else {
            sort(cur.begin(), cur.end(), [](int a, int b) {
                return P[a].cell < P[b].cell;
            });

            int m = (int)cur.size();

            for (int l = 0; l < m; ) {
                int cid = P[cur[l]].cell;
                int r = l + 1;

                while (r < m && P[cur[r]].cell == cid) r++;

                Cell& c = cells[cid];
                Source src(cur, l, r, c.gx, c.gy);
                process_group(src, depth, nxt);

                l = r;
            }
        }

        cur.swap(nxt);
        depth++;
    }

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

---

This editorial was generated by gpt-5.5-high.