概要

各花火ごとに高橋君と青木君の距離を計算し、距離が \(R\) 以下のものを数える問題です。全 \(N\) 発について条件を満たす回数を合計して出力します。

考察

花火 \(i\) 発目での二人の距離は
\(\sqrt{(X_i-P_i)^2 + (Y_i-Q_i)^2}\) です。これが \(R\) 以下かどうかを判定したいですが、毎回平方根を計算すると遅くなる・誤差の心配が出ることがあります。

そこで重要な気づきは、「平方根を取らずに比較できる」ことです。
距離が \(R\) 以下である条件 \(\sqrt{(X_i-P_i)^2 + (Y_i-Q_i)^2} \le R\) は、両辺を二乗して（両辺非負なので同値） \((X_i-P_i)^2 + (Y_i-Q_i)^2 \le R^2\) と書けます。

この形なら整数の四則演算だけで判定でき、誤差がなく高速です。
また \(N \le 10^5\) なので、各花火について1回ずつ計算する素朴な \(O(N)\) の方法で十分間に合います（花火同士の組合せを調べるような \(O(N^2)\) は不要で、すると確実にTLEします）。

例：\(R=5\)、差が \((dx,dy)=(3,4)\) なら \(dx^2+dy^2=9+16=25 \le 25\) なので「一緒に観た」です。

アルゴリズム

1. 入力で \(R^2\) を計算しておく。
2. 各花火 \(i=1..N\) について
   • \(dx=X_i-P_i\), \(dy=Y_i-Q_i\) を計算
   • \(dx^2+dy^2 \le R^2\) なら答えを1増やす
3. 合計を出力する。

計算量

• 時間計算量: \(O(N)\)（各花火につき定数回の計算）
• 空間計算量: \(O(1)\)（入力を逐次処理し、追加の配列を持たない）

実装のポイント

• 平方根（sqrt）は使わず、\(R^2\) と \(dx^2+dy^2\) を比較する。

• 座標や \(R\) は最大 \(10^9\) なので二乗すると最大 \(10^{18}\) 程度になります。Python の整数は桁あふれしないので安全です（他言語なら 64bit 整数を使う）。

• 入力が大きいので sys.stdin.buffer.read().split() のような高速入力を使うと安定します。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    R = int(next(it))
    R2 = R * R

    ans = 0
    for _ in range(N):
        x = int(next(it)); y = int(next(it))
        p = int(next(it)); q = int(next(it))
        dx = x - p
        dy = y - q
        if dx*dx + dy*dy <= R2:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。