Overview

This problem asks us to find the shortest path in a graph where the mothership, debris, and the space station are vertices, and edges exist between locations at a distance of at most \(D\).

However, since checking all edges is too slow, we speed up Breadth-First Search (BFS) using spatial partitioning with a grid and the upper envelope of circular arcs.

Analysis

1. The Minimum Number of Jumps Can Be Found with BFS

Since every jump has a cost of \(1\), the minimum number of jumps can be found using BFS.

However, moving directly from the mothership to the space station is prohibited. Therefore, we first register debris reachable from the mothership as vertices at distance \(1\), and subsequently search via debris.

The challenge is how to find reachable destinations from each piece of debris. Computing the distance between all pairs of debris would take \(O(N^2)\), which is too slow for \(N \leq 10^5\).

2. Partitioning into a Grid of Side Length \(D/2\)

We partition the plane into squares of side length \(D/2\) and group each piece of debris into the cell it belongs to.

The cell coordinates for a point \((x,y)\) are computed as follows:

\((g_x,g_y)=\left(\left\lfloor \frac{2x}{D}\right\rfloor,\left\lfloor \frac{2y}{D}\right\rfloor\right)\)

This partitioning has two important properties.

Any Two Pieces of Debris in the Same Cell Can Reach Each Other

The diagonal length of a cell is:

\(\sqrt{(D/2)^2+(D/2)^2}=\frac{D}{\sqrt{2}}<D\)

Therefore, debris within the same cell can always reach each other in \(1\) jump.

When a piece of debris in a cell is reached for the first time, let its shortest distance be \(k\). Any remaining debris in that cell can be reached in at most \(k+1\) jumps.

Thus, the shortest distances of debris in a single cell take at most two values: \(k\) and \(k+1\). Consequently, a single cell acts as a source in BFS for at most \(2\) layers.

Only the Surrounding \(24\) Cells Need to Be Checked

If the difference in cell coordinates along either axis is \(3\) or more, the distance between points is strictly greater than \(D\).

Therefore, for moves to a different cell, it suffices to check only the surrounding \(24\) cells satisfying:

\(-2 \leq \Delta g_x \leq 2,\qquad -2 \leq \Delta g_y \leq 2\)

3. Partitioning into a Grid Alone Is Not Enough

Many pieces of debris may be concentrated in a single cell.

When there are \(a\) pieces of debris in the source cell and \(b\) pieces in the target cell, checking all pairs takes \(O(ab)\). Just partitioning into a grid cannot avoid \(O(N^2)\) in the worst case.

Therefore, we need to efficiently answer the following query:

Among the set of sources in the current BFS layer, is there any debris that can reach the target point?

To make this determination, we use the upper envelope of circular arcs.

Algorithm

1. Determining Reachability Using the Right Boundary of Circles

First, consider the case where the target cell is to the right of the source cell.

Let a source piece of debris be \(p=(x_p,y_p)\). The reachable region from \(p\) is the interior of a circle with center \(p\) and radius \(D\).

At height \(t\), the \(x\)-coordinate of the right boundary of this circle is:

\(f_p(t)=x_p+\sqrt{D^2-(t-y_p)^2}\)

Note that this is defined only in the range \(|t-y_p|\leq D\).

The target point \(q=(x_q,y_q)\) is to the right of all sources. Hence, the condition that it is reachable from at least one source is:

\(x_q\leq \max_p f_p(y_q)\)

In other words, if we can identify the circle that reaches furthest to the right at height \(y_q\), we only need to check the distance to that circle’s center.

2. Constructing the Upper Envelope of Circular Arcs

For multiple functions \(f_p(t)\), the function formed by their pointwise maximum is called the upper envelope.

In the code, Envelope maintains the following information:

• The circular arc that reaches furthest to the right in each interval
• The first integer coordinate start where that arc becomes the best

Considering the right semicircles of equal radius, between two arcs with different center heights, which one is further to the right switches at most once within their common domain. As height increases, the dominant arc switches from the one with the lower center to the one with the higher center.

Using this property, we construct it via the following steps:

1. Sort the sources by the height (\(y\)-coordinate) of their centers.
2. If heights are equal, keep only the rightmost center.
3. Add arcs one by one.
4. Pop arcs from the end if they become obsolete.
5. Binary search for the first integer coordinate where the new arc becomes dominant.

For a query, binary searching over the start values finds the best arc at that height.

Finally, we perform a standard distance check between the candidate center and the target point. Even if no circle reaches that height, this distance check correctly determines that it is unreachable.

3. Handling Left, Up, and Down Directions via Coordinate Transformations

Directions other than right can be handled with the same logic by flipping or swapping coordinates.

Direction	Transformed Coordinates
Right	\((x,y)\)
Left	\((-x,y)\)
Up	\((y,x)\)
Down	\((-y,x)\)

If the horizontal cell coordinate differs from the target cell, we process it as right or left. If they are the same, we process it as up or down.

For each source cell, we only construct envelopes in the required directions and reuse them for target cells in the same direction.

4. Advancing BFS Cell by Cell

For each cell, we manage debris partitioned into three sets:

• remaining: Debris that has not been reached yet
• frontier: Debris reached in the current BFS layer
• next: Debris to be reached in the next BFS layer

Initially, debris within distance \(D\) of the mothership is placed in frontier, and the current jump count is set to depth = 1.

Then, for each cell whose frontier is non-empty, we do the following:

1. Discover all unreached debris in the same cell.
   Since any debris within the same cell is guaranteed to be reachable, they are all moved to next.

2. Check the surrounding \(24\) cells.
   Construct an envelope from the current cell’s frontier and test reachability for each unreached piece of debris in the target cell.

3. Remove discovered debris from the unreached set.
   Since it is a BFS, the jump count upon first discovery is the shortest.

Debris discovered from the current layer can be reached in depth + 1 jumps. If any of them can reach the station, the answer is depth + 2.

After processing the current layer entirely, we replace frontier with next and proceed to the next layer. If the search finishes without reaching the station, output -1.

5. Why This Approach Finds the Shortest Distance

• Transitions within the same cell are all correctly enumerated.
• For transitions to other cells, all surrounding \(24\) cells that could potentially be reached are checked.
• For each destination, the envelope accurately determines whether it can be reached from any debris in the current layer.
• Newly discovered debris is always used as a source in the next layer.

Therefore, reachable debris is discovered in the exact same order as in a standard BFS with explicit edges, yielding the minimum number of jumps.

Complexity

Let \(C\) be the range size for the binary search over coordinates. In the code, \(C=2\times 10^9+1\).

• Time complexity: Expected \(O(N\log N+N\log C)\)
• Space complexity: \(O(N)\)

Each cell acts as a source in at most \(2\) layers, and the number of adjacent cells is a constant \(24\). Therefore, each unreached piece of debris is queried at most a constant number of times.

Moreover, each piece of debris enters frontier only once. Summing the sorting, construction, and queries of envelopes over the entire algorithm results in the complexity above. The expected time complexity arises from using a hash table for cell lookups.

Implementation Details

Compute Cell Coordinates Using Floor Division Even for Negative Coordinates

Integer division in C++ rounds negative numbers toward zero (truncation), but the floor function is required.

For example, if \(D=4\) and \(x=-1\):

\(\left\lfloor \frac{2x}{D}\right\rfloor=\left\lfloor-\frac12\right\rfloor=-1\)

In the code, gridCoordinate handles negative values separately to compute this correctly.

Avoid Square Roots for Distance Checks

Whether the distance is at most \(D\) is checked via:

\((x_1-x_2)^2+(y_1-y_2)^2\leq D^2\)

Computing purely in integers ensures that points on the boundary are handled precisely.

Compare Arcs Using Integer Arithmetic

In envelope construction, expressions containing two square roots must be compared. Comparing with floating-point numbers risks inaccuracies in determining transition coordinates.

In better, comparisons are done purely in integer arithmetic by rearranging terms and squaring while tracking signs. Since intermediate products can exceed 64-bit integers, __int128_t is used.

Do Not Mix the Current and Next Layers

If newly discovered debris were added to frontier immediately, it would correspond to making multiple jumps within the same BFS layer. Always add them to next and swap them after the current layer has been completely processed.

Remove Discovered Debris in Constant Time

When removing an element from remaining, move the last element to the position being removed and call pop_back(). Since order is not important, this technique allows \(O(1)\) deletion per element.

Source Code

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

using ll = long long;
using i128 = __int128_t;
using ull = unsigned long long;

struct Hash {
    static ull splitmix64(ull x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(ull x) const {
        static const ull seed =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + seed);
    }
};

struct Point {
    ll x, y;
};

struct Cell {
    int gx, gy;
    vector<int> remaining, frontier, next;
    array<int, 24> neighbor;
};

struct Arc {
    ll x, y;
    int id;
    int start;
};

class Envelope {
    static constexpr int MIN_T = -1000000000;
    static constexpr int MAX_T = 1000000000;

    ll d, d2;
    vector<Arc> hull;

    bool better(const Arc& a, const Arc& b, ll t) const {
        if (t < a.y - d) return false;
        if (t > b.y + d) return true;

        ll da = t - a.y;
        ll db = t - b.y;
        ll va = d2 - da * da;
        ll vb = d2 - db * db;
        ll delta = a.x - b.x;
        ll delta2 = delta * delta;

        if (delta >= 0) {
            if (va >= vb) return true;
            ll z = vb - va - delta2;
            if (z <= 0) return true;
            return (i128)4 * delta2 * va >= (i128)z * z;
        } else {
            if (va < vb) return false;
            ll z = va - vb - delta2;
            if (z < 0) return false;
            return (i128)z * z >= (i128)4 * delta2 * vb;
        }
    }

public:
    Envelope(ll distance) : d(distance), d2(distance * distance) {}

    void build(const vector<int>& ids, const vector<Point>& points, int direction) {
        vector<Arc> arcs;
        arcs.reserve(ids.size());

        for (int id : ids) {
            const auto& p = points[id];
            ll x, y;
            if (direction == 0) {
                x = p.x;
                y = p.y;
            } else if (direction == 1) {
                x = -p.x;
                y = p.y;
            } else if (direction == 2) {
                x = p.y;
                y = p.x;
            } else {
                x = -p.y;
                y = p.x;
            }
            arcs.push_back({x, y, id, MIN_T});
        }

        sort(arcs.begin(), arcs.end(), [](const Arc& a, const Arc& b) {
            if (a.y != b.y) return a.y < b.y;
            return a.x > b.x;
        });

        hull.reserve(arcs.size());

        for (size_t i = 0; i < arcs.size();) {
            Arc a = arcs[i];
            size_t j = i + 1;
            while (j < arcs.size() && arcs[j].y == a.y) ++j;
            i = j;

            while (!hull.empty() && better(a, hull.back(), hull.back().start)) {
                hull.pop_back();
            }

            if (hull.empty()) {
                a.start = MIN_T;
                hull.push_back(a);
                continue;
            }

            if (!better(a, hull.back(), MAX_T)) continue;

            int lo = hull.back().start + 1;
            int hi = MAX_T;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (better(a, hull.back(), mid)) hi = mid;
                else lo = mid + 1;
            }

            a.start = lo;
            hull.push_back(a);
        }
    }

    int query(ll t) const {
        int lo = 0, hi = (int)hull.size();
        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;
            if (hull[mid].start <= t) lo = mid;
            else hi = mid;
        }
        return hull[lo].id;
    }
};

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

    int N;
    ll W, D;
    cin >> N >> W >> D;
    const ll D2 = D * D;

    vector<Point> points(N);
    vector<Cell> cells;
    cells.reserve(N);

    unordered_map<ull, int, Hash> index;
    index.max_load_factor(0.7f);
    index.reserve(N);

    auto key = [](int x, int y) -> ull {
        return (ull)(uint32_t)x << 32 | (uint32_t)y;
    };

    auto gridCoordinate = [&](ll x) -> int {
        ll v = 2 * x;
        if (v >= 0) return (int)(v / D);
        return (int)(-((-v + D - 1) / D));
    };

    for (int i = 0; i < N; ++i) {
        cin >> points[i].x >> points[i].y;
        int gx = gridCoordinate(points[i].x);
        int gy = gridCoordinate(points[i].y);
        ull k = key(gx, gy);

        auto [it, inserted] = index.emplace(k, (int)cells.size());
        if (inserted) {
            cells.emplace_back();
            cells.back().gx = gx;
            cells.back().gy = gy;
        }
        cells[it->second].remaining.push_back(i);
    }

    auto reachesGoal = [&](int id) {
        ll x = points[id].x;
        ll y = W - points[id].y;
        return x * x + y * y <= D2;
    };

    vector<int> active, nextActive;
    active.reserve(cells.size());
    nextActive.reserve(cells.size());

    for (int c = 0; c < (int)cells.size(); ++c) {
        auto& cell = cells[c];
        auto& rem = cell.remaining;
        size_t i = 0;
        while (i < rem.size()) {
            int id = rem[i];
            ll x = points[id].x, y = points[id].y;
            if (x * x + y * y <= D2) {
                if (reachesGoal(id)) {
                    cout << 2 << '\n';
                    return 0;
                }
                cell.frontier.push_back(id);
                rem[i] = rem.back();
                rem.pop_back();
            } else {
                ++i;
            }
        }
        if (!cell.frontier.empty()) active.push_back(c);
    }

    if (active.empty()) {
        cout << -1 << '\n';
        return 0;
    }

    array<int, 24> dxs, dys, directions;
    int count = 0;
    for (int dx = -2; dx <= 2; ++dx) {
        for (int dy = -2; dy <= 2; ++dy) {
            if (dx == 0 && dy == 0) continue;
            dxs[count] = dx;
            dys[count] = dy;
            directions[count] = dx > 0 ? 0 : dx < 0 ? 1 : dy > 0 ? 2 : 3;
            ++count;
        }
    }

    for (auto& cell : cells) {
        for (int j = 0; j < 24; ++j) {
            auto it = index.find(key(cell.gx + dxs[j], cell.gy + dys[j]));
            cell.neighbor[j] = it == index.end() ? -1 : it->second;
        }
    }

    int depth = 1;

    auto enqueue = [&](int c, int id) {
        if (cells[c].next.empty()) nextActive.push_back(c);
        cells[c].next.push_back(id);
    };

    while (!active.empty()) {
        for (int c : active) {
            auto& cell = cells[c];

            for (int id : cell.remaining) {
                if (reachesGoal(id)) {
                    cout << depth + 2 << '\n';
                    return 0;
                }
                enqueue(c, id);
            }
            cell.remaining.clear();

            array<unique_ptr<Envelope>, 4> envelopes;

            for (int j = 0; j < 24; ++j) {
                int target = cell.neighbor[j];
                if (target == -1 || cells[target].remaining.empty()) continue;

                int direction = directions[j];
                if (!envelopes[direction]) {
                    envelopes[direction] = make_unique<Envelope>(D);
                    envelopes[direction]->build(cell.frontier, points, direction);
                }

                auto& envelope = *envelopes[direction];
                auto& rem = cells[target].remaining;

                size_t k = 0;
                while (k < rem.size()) {
                    int id = rem[k];
                    ll t = direction < 2 ? points[id].y : points[id].x;
                    int source = envelope.query(t);

                    ll dx = points[id].x - points[source].x;
                    ll dy = points[id].y - points[source].y;

                    if (dx * dx + dy * dy <= D2) {
                        if (reachesGoal(id)) {
                            cout << depth + 2 << '\n';
                            return 0;
                        }
                        enqueue(target, id);
                        rem[k] = rem.back();
                        rem.pop_back();
                    } else {
                        ++k;
                    }
                }
            }

            cell.frontier.clear();
        }

        for (int c : nextActive) {
            cells[c].frontier.swap(cells[c].next);
        }
        active.swap(nextActive);
        nextActive.clear();
        ++depth;
    }

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

---

This editorial was generated by gpt-6-astra-medium.