Overview

Given \(N\) fireworks, you are provided with the coordinates of Takahashi and Aoki at the moment each firework is launched. The problem asks you to find how many fireworks are launched when the Euclidean distance between the two is at most \(R\).

Analysis

The following two points are important for solving this problem.

1. Avoiding Floating-Point Precision Issues

The condition that the distance between the two is at most \(R\) can be expressed as: $\(\sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2} \leq R\)$

If we try to compute this expression directly, we would need to handle floating-point numbers (float type) when computing the square root (\(\sqrt{\quad}\)) on the left side. However, since floating-point numbers are subject to rounding errors, there is a possibility of incorrect judgments near boundary values (which can cause WA).

Instead, we square both sides of the inequality: $\((X_i - P_i)^2 + (Y_i - Q_i)^2 \leq R^2\)$

By comparing “squared distances” in this way, all computations can be performed within the range of integers, enabling exact judgments without any errors.

2. Handling Large Numbers

Looking at the constraints, \(R\) can be up to \(10^9\), and the difference in coordinates can be up to approximately \(2 \times 10^9\). Therefore, the squared values can become very large numbers, up to approximately \(4 \times 10^{18}\). Python natively supports arbitrary-precision integers (integers of any precision), so even such large numbers can be computed without worrying about overflow.

Algorithm

1. Precompute the squared threshold \(R^2\).
2. For each firework, repeat the following steps:
   • Compute the difference in \(x\)-coordinates \(dx\) and the difference in \(y\)-coordinates \(dy\) between Takahashi and Aoki.
   • Compute the squared distance \(dist\_sq = dx^2 + dy^2\).
   • If \(dist\_sq \leq R^2\), increment the count by 1.
3. Output the final count.

Complexity

• Time Complexity: \(O(N)\) Since we loop through each of the \(N\) fireworks once to perform the computation, the processing finishes in time proportional to the number of fireworks \(N\).
• Space Complexity: \(O(N)\) In this implementation, we use sys.stdin.read().split() to read all input at once, so the memory usage is proportional to the input size.

Implementation Notes

• Fast Input Processing: Since \(N\) can be as large as \(10^5\), reading all input at once with sys.stdin.read().split() is faster than repeatedly calling input().

• Using Iterators: By using the pattern zip(it, it, it, it), we can efficiently extract groups of 4 elements (\(X_i, Y_i, P_i, Q_i\)) from a flat list.

• Avoiding Square Roots: As discussed in the analysis, by comparing squared values without using math.sqrt or similar functions, we achieve safe and fast judgments.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.