概要

座標 \((0, 0)\) にある Wi-Fi ルーターから、各建物の座標 \((X_i, Y_i)\) までの距離を計算し、その距離が \(D\) を超えている（電波が届かない）建物の総数を求める問題です。

考察

この問題を解くためのポイントは、「2点間の距離の比較」をいかに効率的かつ正確に行うかです。

1. 距離の計算と浮動小数点の回避

2点間の距離はユークリッド距離の公式 \(\sqrt{X_i^2 + Y_i^2}\) で求められます。電波が届かない条件は \(\sqrt{X_i^2 + Y_i^2} > D\) です。 しかし、平方根（\(\sqrt{\quad}\)）の計算は計算コストが比較的高いだけでなく、浮動小数点数（float）として扱う際に精度誤差が生じる可能性があります。

不等式の両辺はともに 0 以上であるため、両辺を2乗しても大小関係は変わりません。 $\(\sqrt{X_i^2 + Y_i^2} > D \iff X_i^2 + Y_i^2 > D^2\)$ このように「2乗した値」を比較することで、整数（int）のまま正確かつ高速に判定を行うことができます。

2. 大量データの入力処理

本問題では建物の数 \(N\) が最大 \(2 \times 10^5\) と多いため、Pythonの標準的な input() 関数を繰り返し呼び出すと、入力処理だけで制限時間を超えてしまう（TLE）可能性があります。 sys.stdin.read().split() を使用して全ての入力を一括で読み込み、イテレータなどで処理することで、高速な実行が可能になります。

アルゴリズム

1. 判定基準となる距離の2乗 \(D^2\) をあらかじめ計算しておく。
2. 各建物の座標 \((X_i, Y_i)\) について、以下の処理を繰り返す：
   • 原点からの距離の2乗 \(X_i^2 + Y_i^2\) を計算する。
   • 計算した値が \(D^2\) よりも大きい場合、カウントを 1 増やす。
3. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\) \(N\) 棟の建物に対してそれぞれ 1 回ずつ計算と判定を行うため、建物数に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 全ての入力を sys.stdin.read() で一括してメモリに読み込むため、入力サイズに応じたメモリを消費します。

実装のポイント

• map と next の活用: 座標が \(X_1, Y_1, X_2, Y_2, \dots\) と並んでいるデータに対して、map(int, data) で作ったイテレータから next() を使って 2 つずつ取り出すことで、簡潔に座標ペアを取得できます。

• 2乗の比較: x**2 + y**2 > d**2 と書くよりも、x * x + y * y > d_squared と書く方が、べき乗演算のオーバーヘッドを避けられるため、わずかに高速です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # 大量の入力データ（N=2*10^5）を効率的に処理するために sys.stdin.read().split() を使用
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 建物の数 N と 電波の届く最大距離 D を取得
    n = int(data[0])
    d = int(data[1])
    
    # 距離の比較において、計算コストの高い平方根（sqrt）を避けるため、
    # 距離の2乗（D^2）を基準値として計算する
    d_squared = d * d
    
    # 各建物の座標 (Xi, Yi) は data[2] 以降に格納されている
    # 座標データを整数のイテレータに変換する
    it = map(int, data[2:])
    
    not_reachable_count = 0
    
    # n 回ループを回し、各建物の座標を取得して判定を行う
    # x = Xi, y = Yi
    for x in it:
        try:
            y = next(it)
        except StopIteration:
            break
            
        # ユークリッド距離の2乗 (x^2 + y^2) が D^2 より大きい場合、電波は届かない
        if x * x + y * y > d_squared:
            not_reachable_count += 1
            
    # 結果を出力
    print(not_reachable_count)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。