概要

花火ごとに高橋君と青木君の座標が与えられ、二人のユークリッド距離がR以下である花火の数を求める問題です。

考察

この問題は、各花火について高橋君の座標\((X_i, Y_i)\)と青木君の座標\((P_i, Q_i)\)の距離を計算し、それがR以下かどうかを判定すればよい問題です。ただし、制約条件として\(N\)が最大\(10^5\)まで大きくなる可能性があるため、効率的な計算が必要です。

重要な点は、ユークリッド距離を直接計算する代わりに、距離の二乗を比較することで平方根の計算を避けられることです。なぜなら、\(\sqrt{a} \leq R\) は \(a \leq R^2\) と等価だからです。平方根の計算は浮動小数点数の演算となり、誤差が生じる可能性がありますが、整数の二乗比較では誤差が発生せず、かつ計算コストも低くなります。

アルゴリズム

1. 入力から花火の数\(N\)と閾値\(R\)を読み取る
2. \(R\)の二乗\(R^2\)を事前に計算する
3. 各花火について以下の処理を行う：
   • 高橋君の座標\((X_i, Y_i)\)と青木君の座標\((P_i, Q_i)\)を読み取る
   • X座標の差の二乗\((X_i - P_i)^2\)とY座標の差の二乗\((Y_i - Q_i)^2\)を計算する
   • これらの和が\(R^2\)以下かどうかを判定する
   • 条件を満たす場合はカウントを増やす
4. 最終的なカウントを出力する

計算量

• 時間計算量: \(O(N)\)
  • 各花火に対して定数時間で処理を行うため
• 空間計算量: \(O(1)\)
  • 入力データを読み取りながら処理するため、追加のメモリ使用量は定数

実装のポイント

• 浮動小数点数の計算を避けるため、距離の二乗を比較する

• 大きな数値の二乗を計算する際にオーバーフローしないよう注意（Pythonでは整数の範囲が広いため問題ない）

• 入力データを一括で読み取ることで効率的な処理を実現

• 各座標値は整数であるため、二乗計算も整数で正確に行える

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    R = int(data[1])
    R_sq = R * R
    
    count = 0
    index = 2
    for _ in range(n):
        x = int(data[index])
        y = int(data[index+1])
        p = int(data[index+2])
        q = int(data[index+3])
        index += 4
        
        dx = x - p
        dy = y - q
        dist_sq = dx * dx + dy * dy
        
        if dist_sq <= R_sq:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。