概要

\(N\) 発の花火それぞれについて、高橋君と青木君のユークリッド距離が \(R\) 以下かどうかを判定し、条件を満たす花火の数を数える問題です。

考察

• 各花火について、二人の座標が与えられるので、ユークリッド距離を計算して \(R\) と比較すればよいです。
• ユークリッド距離の式は \(\sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2}\) ですが、平方根を取ると浮動小数点の誤差が生じる可能性があります。
• そこで、距離 \(\leq R\) という条件を両辺を二乗して比較します：

\[\sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2} \leq R\]

は、両辺が非負なので、

\[(X_i - P_i)^2 + (Y_i - Q_i)^2 \leq R^2\]

と同値です。これにより浮動小数点演算を一切使わず、整数の演算だけで正確に判定できます。

• 素朴に各花火について \(O(1)\) で判定するだけなので、全体で \(O(N)\) となり、\(N \leq 10^5\) に対して十分高速です。特別なアルゴリズムは不要です。

アルゴリズム

1. \(N\) と \(R\) を読み込み、\(R^2\) を事前に計算しておく。
2. 各花火 \(i\) について以下を行う：
   • \(dx = X_i - P_i\)、\(dy = Y_i - Q_i\) を計算する。
   • \(dx^2 + dy^2 \leq R^2\) であれば、カウントを \(1\) 増やす。
3. 最終的なカウントを出力する。

具体例: \(R = 5\)、高橋君 \((1, 2)\)、青木君 \((4, 6)\) の場合

• \(dx = 1 - 4 = -3\)、\(dy = 2 - 6 = -4\)
• \(dx^2 + dy^2 = 9 + 16 = 25\)
• \(R^2 = 25\)
• \(25 \leq 25\) なので「一緒に観た」と判定される（距離ちょうど \(5\)）

計算量

• 時間計算量: \(O(N)\) — 各花火について定数時間の計算を行う
• 空間計算量: \(O(N)\) — 入力データの読み込み分（逐次読み込みにすれば \(O(1)\) も可能）

実装のポイント

• 平方根を使わない: sqrt を使うと浮動小数点誤差で誤判定する恐れがあります。両辺を二乗して整数のまま比較するのが鉄則です。

• オーバーフローに注意: 座標の値が最大 \(10^9\) なので、\(dx\) は最大 \(2 \times 10^9\)、\(dx^2\) は最大 \(4 \times 10^{18}\) になります。C++ などでは 64 ビット整数（long long）が必要ですが、Python は多倍長整数を標準でサポートしているため問題ありません。

• 高速な入力: \(N\) が最大 \(10^5\) なので、Python では sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    R = int(input_data[idx]); idx += 1
    R2 = R * R
    count = 0
    for _ in range(N):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        p = int(input_data[idx]); idx += 1
        q = int(input_data[idx]); idx += 1
        dx = x - p
        dy = y - q
        if dx * dx + dy * dy <= R2:
            count += 1
    print(count)

main()

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