概要

各建物がルーター（原点）から距離 \(D\) 以内かどうかを判定し、届かない（距離が \(D\) より大きい）建物の数を数える問題です。

考察

建物 \((X_i, Y_i)\) と原点 \((0,0)\) のユークリッド距離は \(\sqrt{X_i^2 + Y_i^2}\) です。
電波が届かない条件は - \(\sqrt{X_i^2 + Y_i^2} > D\)

ですが、ここで平方根を毎回計算すると計算が重くなるうえ、浮動小数点の誤差で境界（ちょうど距離 \(D\)）付近の判定が不安定になる可能性があります。

そこで両辺を二乗して比較します。\(D \ge 0\) なので不等号の向きは変わらず、 - \(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)

となります。これなら整数計算だけで正確に判定できます。

例えば \(D=5\) のとき、 - \((3,4)\) は \(3^2+4^2=25\) で \(D^2=25\) 以下なので届く - \((4,4)\) は \(4^2+4^2=32\) で \(25\) より大きいので届かない
のように判定できます。

また \(N\) は最大 \(2\times 10^5\) なので、各点を1回ずつ見る \(O(N)\) の処理が必要十分です（全組み合わせなどは不要）。

アルゴリズム

1. 入力で \(N, D\) を受け取る。
2. \(D^2\) を計算しておく（\(D2 = D \times D\)）。
3. 各建物について \(S = X_i^2 + Y_i^2\) を計算する。
4. もし \(S > D2\) なら電波が届かないのでカウントを1増やす。
5. 最後にカウントを出力する。

計算量

• 時間計算量: \(O(N)\)（各建物を1回ずつ判定）
• 空間計算量: \(O(1)\)（カウンタなど定数個のみ）

実装のポイント

• 判定は \(\sqrt{...}\) を使わず、\(X_i^2 + Y_i^2\) と \(D^2\) の比較にする（誤差なし・高速）。

• \(N\) が大きいので、Pythonでは sys.stdin.buffer.read() のような高速入力が有効です。

• 座標は負でも、二乗するので問題ありません（\(x*x\) は常に非負）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    D = int(next(it))
    D2 = D * D

    cnt = 0
    for _ in range(N):
        x = int(next(it))
        y = int(next(it))
        if x * x + y * y > D2:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。