Overview

For each firework, the coordinates of Takahashi and Aoki are given, and we need to find the number of fireworks where the Euclidean distance between the two is at most R.

Analysis

This problem requires calculating the distance between Takahashi’s coordinates \((X_i, Y_i)\) and Aoki’s coordinates \((P_i, Q_i)\) for each firework, and determining whether that distance is at most R. However, since the constraint allows \(N\) to be as large as \(10^5\), efficient computation is necessary.

The key insight is that instead of directly computing the Euclidean distance, we can compare the squared distances to avoid computing square roots. This is because \(\sqrt{a} \leq R\) is equivalent to \(a \leq R^2\). Computing square roots involves floating-point arithmetic, which can introduce errors, whereas comparing squared integers produces no errors and also has lower computational cost.

Algorithm

1. Read the number of fireworks \(N\) and the threshold \(R\) from input
2. Precompute \(R\) squared, i.e., \(R^2\)
3. For each firework, perform the following:
   • Read Takahashi’s coordinates \((X_i, Y_i)\) and Aoki’s coordinates \((P_i, Q_i)\)
   • Compute the squared difference in X-coordinates \((X_i - P_i)^2\) and the squared difference in Y-coordinates \((Y_i - Q_i)^2\)
   • Determine whether their sum is at most \(R^2\)
   • If the condition is satisfied, increment the count
4. Output the final count

Complexity

• Time complexity: \(O(N)\)
  • Each firework is processed in constant time
• Space complexity: \(O(1)\)
  • Since we process the data as we read the input, the additional memory usage is constant

Implementation Notes

• Compare squared distances to avoid floating-point arithmetic

• Be careful about overflow when computing squares of large numbers (in Python, this is not an issue due to arbitrary-precision integers)

• Achieve efficient processing by reading input data in bulk

• Since all coordinate values are integers, squared computations can be performed exactly with integers

  Source Code

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

This editorial was generated by deepseekv3.