Overview

This problem asks for the minimum number of jumps required to travel from \((0,0)\) to \((0,W)\) using points on a plane (debris) as stepping stones, where the distance of a single move must be \(\le D\). Since this is a shortest path problem on an unweighted graph where all edge weights are 1, it can be solved with BFS. However, because there can be up to \(O(N^2)\) edges, we need to use a spatial data structure to efficiently perform “neighborhood point enumeration + extraction”.

Analysis

Graph Formulation

Let the vertices be the “mothership \((0,0)\)”, “each piece of debris \((x_i,y_i)\)”, and the “station \((0,W)\)”, and add an edge between any two points with a distance of \(D\) or less. However, we do not add an edge directly from “mothership \(\to\) station” (because we must visit at least one piece of debris).

Since every edge has a cost of 1, minimum number of jumps = shortest path with minimum number of edges = BFS.

Issues with the Naive Approach

If we naively construct all adjacency relations, for \(N \le 10^5\), there are roughly \(5\times10^9\) pairs of points, resulting in TLE and MLE just from constructing the edges. In other words, the core of this problem is that we must not build the adjacency list explicitly.

Key Observation: Each Point is Used Only Once in BFS

In BFS, once the distance to a vertex is determined, it is never updated again. Therefore, it is sufficient if we can quickly perform the operation:

“Extract all unvisited points within distance \(D\) of the current location \((cx,cy)\).”

Moreover, extracted points can be deleted from the structure, so performing neighborhood queries with deletion a total of \(N\) times will complete the BFS. Because of deletions, the “total number of extracted points” is bounded by \(N\), which is key because the total output size across all queries remains small.

Implementing Neighborhood Queries

Therefore, we store the set of points in a quadtree (a k-d tree also works). By storing the following in each node:

• cnt: The number of (undeleted) points contained in the node
• \([\text{minx},\text{maxx}]\times[\text{miny},\text{maxy}]\): The bounding box of the points contained in the node

during a query we can prune as follows:

• Immediately skip nodes where cnt == 0
• Immediately skip nodes where the minimum distance from the current location to the bounding box exceeds \(D\)

allowing us to efficiently collect only points inside the circle. The collected points are removed from the leaf lists, and the cnt of their ancestors is decremented.

(As an alternative approach, one can also “bucket into a grid with side length \(D/\sqrt{2}\) and only inspect around \(5\times5\) neighboring cells”. This can be implemented by hashing the coordinates with a dictionary/hash map. The advantage of a quadtree is that it runs stably regardless of the distribution of coordinates.)

Algorithm

1. Read the input and construct a quadtree over all debris.
   • Recursively subdivide each node into 4 children until the number of points is at or below a threshold (e.g., 16).
   • Store the point count cnt and the bounding box of the actual points in each node.
2. Extract all debris within distance \(D\) of the mothership \((0,0)\) using query(0,0), and enqueue them into the BFS queue with distance 1 (simultaneously deleting them from the tree).
3. Each time a point \(u=(x_u,y_u)\) is popped from the queue:
   • First, check whether it can reach the station: If \(x_u^2+(y_u-W)^2 \le D^2\), the answer is dist[u]+1, and we terminate (since this is BFS, the first found distance is minimal).
   • Otherwise, call query(x_u,y_u) to extract unvisited debris within distance \(D\), and push them to the queue with dist = dist[u]+1.
4. If the queue becomes empty and the station has not been reached, output -1.

Since BFS processes vertices in non-decreasing order of distance, dist[u]+1 when the station is first reached is the answer.

Complexity

Let \(N\) be the number of points and \(h\) be the height of the quadtree (roughly \(O(\log N)\), worst-case depends on the coordinate range):

• Tree construction: \(O(N \log N)\)

• Point extraction: Each point is extracted exactly once, and updating ancestors’ cnt takes \(O(h)\) \(\to\) \(O(N\log N)\) in total.

• Query search cost: Due to pruning, we only traverse nodes that intersect the circle. The theoretical worst-case is around \(O(\sqrt N)\) per query, leading to \(O(N\sqrt N)\) in total, but in practice it is extremely fast because deletions continually shrink the tree.

• Time complexity: \(O(N\sqrt{N})\) (worst-case estimate, practically around \(O(N\log N)\))

• Space complexity: \(O(N)\)

Implementation Details

• Do not take square roots: Perform distance comparisons in squared form, i.e., \(dx^2+dy^2 \le D^2\), to completely avoid floating-point inaccuracies. Since \(|x|\le 10^9,\ D \le 10^9\), use long long in C++ (values fit comfortably within approximately \(8\times10^{18}\)).

• Disallow moving directly from mothership to station: This condition is naturally satisfied by simply not checking whether \((0,0)\) can reach \((0,W)\) at the start of BFS. Only check for reaching the station upon popping debris from the queue.

• Distance to a bounding box: Calculate the distance along each axis independently as \(dx=\max(\text{minx}-cx,\ 0,\ cx-\text{maxx})\) (and similarly for \(dy\)), and compute \(dx^2+dy^2\).

• When a point is deleted, decrement the cnt of its ancestors, and if necessary recompute the bounding box of the leaf to make pruning even tighter (nodes with cnt == 0 are never visited again).

• Constructing and traversing the tree using an explicit stack instead of recursion avoids recursion depth limits and overhead in Python. Read the input all at once using sys.stdin.buffer.read().split().

• Managing the BFS queue with a list and an index pointer head runs faster than using deque (strict layer-by-layer stratification by distance is not needed, as monotonicity is automatically preserved).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); W = int(data[1]); D = int(data[2])
    D2 = D * D
    xs = [0] * n; ys = [0] * n
    idx = 3
    for i in range(n):
        xs[i] = int(data[idx]); ys[i] = int(data[idx + 1]); idx += 2

    minx = min(xs); maxx = max(xs); miny = min(ys); maxy = max(ys)
    span = max(maxx - minx, maxy - miny) + 1
    size = 1
    while size < span:
        size <<= 1

    LEAF = 16
    cnt = [0]; par = [-1]
    bminx = [0]; bmaxx = [0]; bminy = [0]; bmaxy = [0]
    ch = [0, 0, 0, 0]
    leafpts = [None]

    stack = [(0, list(range(n)), minx, miny, size)]
    while stack:
        v, idxs, x0, y0, sz = stack.pop()
        cnt[v] = len(idxs)
        ax = bx = xs[idxs[0]]; ay = by = ys[idxs[0]]
        for i in idxs:
            x = xs[i]; y = ys[i]
            if x < ax: ax = x
            elif x > bx: bx = x
            if y < ay: ay = y
            elif y > by: by = y
        bminx[v] = ax; bmaxx[v] = bx; bminy[v] = ay; bmaxy[v] = by
        if len(idxs) <= LEAF or sz <= 1:
            leafpts[v] = idxs
            continue
        half = sz >> 1
        mx = x0 + half; my = y0 + half
        q0 = []; q1 = []; q2 = []; q3 = []
        for i in idxs:
            if xs[i] < mx:
                if ys[i] < my: q0.append(i)
                else: q1.append(i)
            else:
                if ys[i] < my: q2.append(i)
                else: q3.append(i)
        b4 = 4 * v
        k = 0
        for q, nx0, ny0 in ((q0, x0, y0), (q1, x0, my), (q2, mx, y0), (q3, mx, my)):
            if q:
                u = len(cnt)
                cnt.append(0); par.append(v)
                bminx.append(0); bmaxx.append(0); bminy.append(0); bmaxy.append(0)
                ch.append(0); ch.append(0); ch.append(0); ch.append(0)
                leafpts.append(None)
                ch[b4 + k] = u
                stack.append((u, q, nx0, ny0, half))
            k += 1

    def query(cx, cy, cnt=cnt, par=par, bminx=bminx, bmaxx=bmaxx, bminy=bminy,
              bmaxy=bmaxy, ch=ch, leafpts=leafpts, xs=xs, ys=ys, D2=D2):
        res = []
        st = [0]
        while st:
            v = st.pop()
            if cnt[v] == 0: continue
            t = bminx[v]
            if cx < t:
                dx = t - cx
            else:
                t = bmaxx[v]
                dx = cx - t if cx > t else 0
            t = bminy[v]
            if cy < t:
                dy = t - cy
            else:
                t = bmaxy[v]
                dy = cy - t if cy > t else 0
            if dx * dx + dy * dy > D2: continue
            lp = leafpts[v]
            if lp is None:
                b = 4 * v
                u = ch[b]
                if u: st.append(u)
                u = ch[b + 1]
                if u: st.append(u)
                u = ch[b + 2]
                if u: st.append(u)
                u = ch[b + 3]
                if u: st.append(u)
            else:
                keep = []
                nf = 0
                for i in lp:
                    ddx = xs[i] - cx; ddy = ys[i] - cy
                    if ddx * ddx + ddy * ddy <= D2:
                        res.append(i); nf += 1
                    else:
                        keep.append(i)
                if nf:
                    leafpts[v] = keep
                    u = v
                    while u >= 0:
                        cnt[u] -= nf
                        u = par[u]
                    if keep:
                        ax = bx = xs[keep[0]]; ay = by = ys[keep[0]]
                        for i in keep:
                            x = xs[i]; y = ys[i]
                            if x < ax: ax = x
                            elif x > bx: bx = x
                            if y < ay: ay = y
                            elif y > by: by = y
                        bminx[v] = ax; bmaxx[v] = bx; bminy[v] = ay; bmaxy[v] = by
        return res

    dist = [0] * n
    ans = -1
    q = query(0, 0)
    for i in q:
        dist[i] = 1
    head = 0
    while head < len(q):
        u = q[head]; head += 1
        xu = xs[u]; yu = ys[u]
        t = yu - W
        if xu * xu + t * t <= D2:
            ans = dist[u] + 1
            break
        nd = dist[u] + 1
        for i in query(xu, yu):
            dist[i] = nd
            q.append(i)
    sys.stdout.write(str(ans) + "\n")

main()

---

This editorial was generated by claude5opus-high.