概要

\(N\) 発の花火について、それぞれの打ち上げ時点における高橋君と青木君の座標が与えられます。二人のユークリッド距離が \(R\) 以下である花火が何発あるかを求める問題です。

考察

この問題を解く上で、以下の2つのポイントが重要になります。

1. 浮動小数点の精度問題を避ける

二人の距離が \(R\) 以下である条件は、以下の式で表されます。 $\(\sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2} \leq R\)$

この式をそのまま計算しようとすると、左辺の平方根（\(\sqrt{\quad}\)）の計算で浮動小数点数（float型）を扱うことになります。しかし、浮動小数点数には計算誤差が伴うため、境界値付近で判定を誤る（WAの原因になる）可能性があります。

そこで、不等式の両辺を2乗して考えます。 $\((X_i - P_i)^2 + (Y_i - Q_i)^2 \leq R^2\)$

このように「距離の2乗」を比較することで、すべての計算を整数の範囲で行うことができ、誤差のない正確な判定が可能になります。

2. 大きな数値への対応

制約を確認すると、\(R\) は最大 \(10^9\)、座標の差は最大 \(2 \times 10^9\) 程度になります。そのため、2乗した値は最大で \(4 \times 10^{18}\) 程度の非常に大きな数になります。 Pythonは標準で多倍長整数（任意の精度の整数）をサポートしているため、このような大きな数でもオーバーフローを気にせず計算できます。

アルゴリズム

1. 閾値 \(R\) を2乗した値 \(R^2\) をあらかじめ計算しておく。
2. 各花火について以下の処理を繰り返す：
   • 高橋君と青木君の \(x\) 座標の差 \(dx\) と \(y\) 座標の差 \(dy\) を求める。
   • 距離の2乗 \(dist\_sq = dx^2 + dy^2\) を計算する。
   • \(dist\_sq \leq R^2\) であれば、カウントを1増やす。
3. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\) \(N\) 発の花火に対して1回ずつループを回して計算を行うため、花火の数 \(N\) に比例した時間で処理が終わります。
• 空間計算量: \(O(N)\) 今回の実装では sys.stdin.read().split() を用いて入力を一度にすべて読み込んでいるため、入力サイズに比例したメモリを使用します。

実装のポイント

• 高速な入力処理: \(N\) が \(10^5\) と比較的大きいため、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込む方が実行時間を短縮できます。

• イテレータの活用: zip(it, it, it, it) という書き方を用いることで、フラットなリストから 4 つずつの要素（\(X_i, Y_i, P_i, Q_i\)）を効率よく取り出すことができます。

• 平方根を使わない: 考察で述べた通り、math.sqrt などを使わずに2乗のまま比較することで、安全かつ高速に判定を行っています。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # これにより、大量の入力データを高速に処理することが可能
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 1つ目の要素は花火の数 N、2つ目の要素は距離の閾値 R
    N = int(data[0])
    R = int(data[1])
    
    # 距離の計算において平方根を避けるため、閾値 R の2乗を計算しておく
    # Pythonは任意の精度の整数を扱えるため、R^2 が 10^18 になっても問題ない
    R_sq = R * R
    
    # 3つ目以降の要素（各花火の座標）を整数に変換するイテレータを作成
    it = map(int, data[2:])
    count = 0
    
    # 各花火について、高橋君の座標 (xi, yi) と青木君の座標 (pi, qi) を取得
    # zip(it, it, it, it) を使うことで、4つずつ要素を取り出すことができる
    for xi, yi, pi, qi in zip(it, it, it, it):
        # 二点間の距離の2乗を計算: (X1-X2)^2 + (Y1-Y2)^2
        dx = xi - pi
        dy = yi - qi
        dist_sq = dx * dx + dy * dy
        
        # 距離の2乗が R の2乗以下であれば、一緒に観たと判定
        if dist_sq <= R_sq:
            count += 1
            
    # 二人が一緒に観た花火の総数を出力
    print(count)

if __name__ == '__main__':
    solve()

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