「距離が \(D\) 以下のデブリ」同士を辺で結んだグラフを構築すれば、結局は 01-BFS をすれば良いです。

このグラフは簡単に \(O(N^2)\) で構築できますが TLE となるでしょう。

---

以下、単に「距離」というと座標平面上かグラフ上かわかりにくいため、（濫用ですが）グラフ上の距離に関しては \(\text{dist}\) と書くことにします。

\(O(N \log N)\) で解く方法がいくつかあります。

改善のための簡単な気持ちとしては、近くの点は必ず結ぶのでわざわざ「距離は \(D\) 以下ですか？」という計算したくはないですし、遠くの点はどうせ結ばないのでこれも計算したくはないです。

---

解法 1 : グリッドに分割する

小さい定数 \(C\) を決め、座標平面全体を \(\dfrac{D}{C}\times\dfrac{D}{C}\) の大きさのグリッドに分割します。（各領域を以下「マス」と呼びます）本解説では、以下 \(C = 2\) とします。（他の小さい定数でも同様の議論が可能です）

同じマスに含まれる \(2\) 点間の距離は最大でも\(\dfrac{D}{\sqrt2}\) ですから、同じマスに存在する頂点は必ず辺で結ばれます。また、あるマスの内部からは、高々周囲の \(25\) マスしか辺が張られないことも計算からわかります。（それ以上は、必ず \(D\) より遠くなります）

そして、マスの内部のある頂点の \(\text{dist}\) が \(k\) と決まれば、その瞬間、内部の他の頂点の \(\text{dist}\) が \(k, k+1\) のどちらかと決まることに注意してください。

---

解法 1 - 1 : KD-Tree を使う

ライブラリに押し付けることでシンプルに書けますが、最悪計算量の保証がない解法です。

\(\text{dist}\) がちょうど \(k\) である頂点の集合 \(V_k\) を考えます。\(V_{k+1}\) を定めるには以下のようにします。

• KD-tree を \(V_k\) を頂点集合として構築する
• \(V_k\) に含まれる頂点の周囲 \(25\) マスを列挙する
• 周囲マスに含まれるすべての頂点 \(p\) について \(q \in V_k\) の最近点距離を調べる
• もし \(p, q\) の距離が \(D\) 以下なら \(p \in V_{k+1}\) である

\(1\) つ目の構築は \(O(|V_k| \log |V_k|)\) で、 \(3\) マス目のクエリ回数も各頂点について高々 \(50\) 回です。

ただし、「KD-tree の最近点距離クエリ」は最悪 \(O(N)\) となる配置が存在します。回転・平行移動などの乱数を加えることで、実用上は高速に動くことが多く、もっとも通されやすい解法だとも考えています。

---

解法 1 - 2 円弧包絡線をもちいる

理論的な計算量保証があり、かつ定数倍も良好な方針です。ただ、ライブラリ等に押し付けられる部分が少ないです。

ある \(V_k\) の点を含むマス \(A\) と、周囲マス \(B\) を考えます。適切に反転・軸の入れ替えをして「 \(A\) より \(B\) が右にある」ようにしておきます。

\(V_k\) の各点と辺をむすべる範囲は、半径 \(D\) の円の内側です。そこで「各高さ \(v\) についてどの円が一番右まで届くか」という包絡線を求めることを考えます。中心を高さの順にならべると、その包絡線上に現れる円もおなじ順に現れます。（微分を比べれば簡単に示せます）

よって、 CHT と同様のアルゴリズムをもちいることで、包絡線を「 \(A\) に含まれる頂点の線形時間」で構築することができます。包絡線の左側にあるかどうかも「 \(B\) に含まれる頂点の線形時間」で判定することができるため、ソートがボトルネックとなり、 \(O(N \log N)\) です。

---

解法 1 - 3 : Voronoi 図を使う

最近点距離クエリは Voronoi 図をもちいることで、頂点集合のサイズを \(S\) として、構築 \(O(S \log S)\) クエリ \(O(\log S)\) で処理できることが知られています。よって、これにより \(O(N \log N)\) も保証されます。

しかし、この実装は KD-Tree に比べると、とても難解かつ重実装であることも同時に知られています。また、理論的な計算量保証はありますが、実際には定数倍がかなり重く TLE となる可能性も否めません。

---

以下の解法は（解説作成者の体力が限界であるため）紹介するに留めることにします。

• 解法 2 : Delaunay 三角形分割をする方法

  グリッドで分けて探索領域を制限する代わりに、Delaunay 三角形分割によって、探索領域を制限します。

  三角形分割に使われた辺のみが候補辺になるわけではないですが、この辺により \(V_k\) が連結であることが示されるため、制限することが可能です。同様に最近点クエリも必要になります。

• 解法 3 : 動的最近点探索をする方法 \(O(N \ \text{poly} (\log N))\)

  もっともふつうの BFS に近い解法です。各頂点について「無駄無く \(\text{dist}\) が \(1\) 大きくなる辺だけを見る」ということができれば、 \(O(N)\) で BFS ができます。

  そのためには、

  • はじめにすべての頂点を候補とした「最近点クエリを処理するデータ構造」をつくる
  • すでに訪問した頂点について、その候補から消す

  といった、動的削除が可能なデータ構造があればよいです。これを実現するデータ構造が存在するようです。（これが正しいことは確認したつもりですが、間違いがあれば削除します）

---

実装例

解法 1-2 の実装例です。Chat GPT による実装です。

import sys
from collections import defaultdict
from math import sqrt

input = sys.stdin.readline


def solve():
    N, W, D = map(int, input().split())

    X = [0] * (N + 1)
    Y = [0] * (N + 1)

    for I in range(N):
        X[I], Y[I] = map(int, input().split())

    S = N
    D2 = D * D

    CELLS = {}
    BELONG = [None] * (N + 1)

    for I in range(N):
        C = (2 * X[I] // D, 2 * Y[I] // D)
        BELONG[I] = C
        CELLS.setdefault(C, []).append(I)

    BELONG[S] = (0, 0)

    BY_X = {
        C: sorted(A, key=lambda I: (X[I], Y[I]))
        for C, A in CELLS.items()
    }
    BY_Y = {
        C: sorted(A, key=lambda I: (Y[I], X[I]))
        for C, A in CELLS.items()
    }

    def UV(P, HORIZONTAL, SIGN):
        if HORIZONTAL:
            return SIGN * X[P], Y[P]
        return SIGN * Y[P], X[P]

    def BUILD(SRC, HORIZONTAL, SIGN):
        A = []

        for P in SRC:
            U, V = UV(P, HORIZONTAL, SIGN)

            if A and UV(A[-1], HORIZONTAL, SIGN)[1] == V:
                if UV(A[-1], HORIZONTAL, SIGN)[0] < U:
                    A[-1] = P
            else:
                A.append(P)

        if not A:
            return [], [], 0

        BASE = UV(A[0], HORIZONTAL, SIGN)[1]
        HULL = []
        START = []

        def SWITCH(P, Q):
            UP, VP = UV(P, HORIZONTAL, SIGN)
            UQ, VQ = UV(Q, HORIZONTAL, SIGN)

            DU = (UQ - UP) / D
            DV = (VQ - VP) / D

            VP = (VP - BASE) / D
            VQ = (VQ - BASE) / D

            Z = sqrt(max(0.0, DV * (2.0 - DV)))

            if DU >= Z:
                return VQ - 1.0

            if DU <= -Z:
                return VP + 1.0

            R2 = DU * DU + DV * DV
            T = sqrt((4.0 - R2) / R2)

            return (VP + VQ - DU * T) * 0.5

        for P in A:
            if not HULL:
                HULL.append(P)
                START.append(float("-inf"))
                continue

            C = SWITCH(HULL[-1], P)

            while len(HULL) >= 2 and C <= START[-1]:
                HULL.pop()
                START.pop()
                C = SWITCH(HULL[-1], P)

            HULL.append(P)
            START.append(max(C, START[-1]))

        return HULL, START, BASE

    DIST = [-1] * (N + 1)
    DIST[S] = 0

    FRONT = [S]
    LAYER = 0

    while FRONT:
        GROUP = defaultdict(list)

        for P in FRONT:
            GROUP[BELONG[P]].append(P)

        NEXT = []

        for C, SRC in GROUP.items():
            GX, GY = C

            if SRC == [S]:
                SRC_X = SRC_Y = SRC
            else:
                SRC_X = [P for P in BY_X[C] if DIST[P] == LAYER]
                SRC_Y = [P for P in BY_Y[C] if DIST[P] == LAYER]

            for Q in CELLS.get(C, ()):
                if DIST[Q] == -1:
                    DIST[Q] = LAYER + 1
                    NEXT.append(Q)

            CACHE = {}

            for DX in range(-2, 3):
                for DY in range(-2, 3):
                    if DX == 0 and DY == 0:
                        continue

                    TC = (GX + DX, GY + DY)

                    if TC not in CELLS:
                        continue

                    if DX != 0:
                        HORIZONTAL = True
                        SIGN = 1 if DX > 0 else -1
                        SRC_SORTED = SRC_Y
                        TGT = BY_Y[TC]
                    else:
                        HORIZONTAL = False
                        SIGN = 1 if DY > 0 else -1
                        SRC_SORTED = SRC_X
                        TGT = BY_X[TC]

                    KEY = (HORIZONTAL, SIGN)

                    if KEY not in CACHE:
                        CACHE[KEY] = BUILD(
                            SRC_SORTED,
                            HORIZONTAL,
                            SIGN
                        )

                    HULL, START, BASE = CACHE[KEY]

                    PTR = 0

                    for Q in TGT:
                        V = Y[Q] if HORIZONTAL else X[Q]
                        Z = (V - BASE) / D

                        while (
                            PTR + 1 < len(HULL)
                            and START[PTR + 1] <= Z
                        ):
                            PTR += 1

                        if DIST[Q] != -1:
                            continue

                        OK = False

                        for J in range(
                            max(0, PTR - 2),
                            min(len(HULL), PTR + 3)
                        ):
                            P = HULL[J]

                            DX2 = X[P] - X[Q]
                            DY2 = Y[P] - Y[Q]

                            if DX2 * DX2 + DY2 * DY2 <= D2:
                                OK = True
                                break

                        if OK:
                            DIST[Q] = LAYER + 1
                            NEXT.append(Q)

        for P in NEXT:
            DX = X[P]
            DY = Y[P] - W

            if DX * DX + DY * DY <= D2:
                print(LAYER + 2)
                return

        FRONT = NEXT
        LAYER += 1

    print(-1)


if __name__ == "__main__":
    solve()