概要

原点にあるWi-Fiルーターから距離 \(D\) 以内にある建物に電波が届くとき、電波が届かない建物の数を求めます。

考察

各建物がルーターから受信できるかどうかは、その建物の座標 \((X_i, Y_i)\) とルーターの位置 \((0, 0)\) とのユークリッド距離が \(D\) 以下かどうかで判定できます。
具体的には、距離は \(\sqrt{X_i^2 + Y_i^2}\) で求められますが、平方根の計算は浮動小数点誤差の原因となることがあります。
そこで、両辺を2乗して比較することで、より安全かつ高速に判定が可能です：
$\(X_i^2 + Y_i^2 \leq D^2\)$
この不等式を満たさない建物の数を数えればよいです。

素朴にすべての建物について距離を計算し、比較する方法でも十分高速ですが、この問題では \(N\) が最大 \(2 \times 10^5\) なので、各計算が定数時間であれば間に合います。

アルゴリズム

1. 入力から \(N\)（建物数）と \(D\)（電波到達距離）を読み込む。
2. 各建物に対して以下を行う：
   • 座標 \((X_i, Y_i)\) を読み込む。
   • \(X_i^2 + Y_i^2\) を計算し、それが \(D^2\) より大きければカウントアップ。
3. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 浮動小数点演算を避けるために、距離の比較は2乗した値で行う。

• 各座標を逐次読み込み、必要な計算だけを行うことでメモリ効率を良くしている。

  ソースコード

import math

# 入力の読み込み
N, D = map(int, input().split())
count = 0

for _ in range(N):
    X, Y = map(int, input().split())
    distance_squared = X**2 + Y**2
    if distance_squared > D**2:
        count += 1

print(count)

この解説は qwen3-coder-480b によって生成されました。