概要

原点にあるWi-Fiルーターから距離 \(D\) より遠い位置にある建物の数を数える問題です。

考察

問題の理解

• Wi-Fiルーターは原点 \((0, 0)\) に設置されています
• 各建物 \((X_i, Y_i)\) について、原点からの距離が \(D\) 以下なら電波が届きます
• 距離が \(D\) より大きい建物の数を求めます

重要な気づき：平方根の計算を避ける

素朴に考えると、各建物について距離 \(\sqrt{X_i^2 + Y_i^2}\) を計算し、\(D\) と比較したくなります。

しかし、平方根の計算には以下の問題があります： 1. 浮動小数点誤差: sqrt 関数は浮動小数点数を返すため、境界値付近で誤差が生じる可能性がある 2. 計算コスト: 平方根の計算は比較的重い処理

解決策：両辺を2乗して比較

距離 \(d_i = \sqrt{X_i^2 + Y_i^2}\) と \(D\) の大小比較は、両辺を2乗しても結果は変わりません（どちらも非負なので）。

つまり： $\(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)$

これにより、整数のみで正確に比較できます。

具体例

例えば \(D = 5\) のとき： - 建物A \((3, 4)\): \(3^2 + 4^2 = 25\)、\(D^2 = 25\)。\(25 > 25\) は偽 → 電波が届く - 建物B \((4, 4)\): \(4^2 + 4^2 = 32\)、\(D^2 = 25\)。\(32 > 25\) は真 → 電波が届かない

アルゴリズム

1. \(D^2\) を事前に計算しておく
2. 各建物 \((X_i, Y_i)\) について：
   • \(X_i^2 + Y_i^2\) を計算
   • これが \(D^2\) より大きければカウントを増やす
3. 最終的なカウントを出力

d_squared = D × D
count = 0
for 各建物(X, Y):
    if X × X + Y × Y > d_squared:
        count += 1
出力: count

計算量

• 時間計算量: \(O(N)\)
  • 各建物について定数時間の計算を1回ずつ行う
• 空間計算量: \(O(1)\)
  • カウンタと座標を保持する変数のみ使用

実装のポイント

1. \(D^2\) の事前計算: ループ内で毎回 d * d を計算するより、ループ外で1回だけ計算しておく方が効率的です

2. オーバーフローに注意: \(X_i, Y_i\) の最大値は \(10^6\) なので、\(X_i^2 + Y_i^2\) の最大値は \(2 \times 10^{12}\) です。Pythonでは整数のオーバーフローはありませんが、C++などでは long long 型を使う必要があります

3. 比較演算子の選択: 「距離が \(D\) 以下なら届く」ので、「届かない」条件は「距離が \(D\) より大きい」、すなわち > を使います（>= ではない）

   ソースコード

n, d = map(int, input().split())
d_squared = d * d
count = 0

for _ in range(n):
    x, y = map(int, input().split())
    if x * x + y * y > d_squared:
        count += 1

print(count)

---

この解説は claude4.5opus によって生成されました。