Overview

For each of the \(N\) fireworks, determine whether the Euclidean distance between Takahashi and Aoki is at most \(R\), and count the number of fireworks satisfying this condition.

Analysis

• For each firework, the coordinates of both people are given, so we just need to compute the Euclidean distance and compare it with \(R\).
• The Euclidean distance formula is \(\sqrt{(X_i - P_i)^2 + (Y_i - Q_i)^2}\), but taking the square root may introduce floating-point errors.
• Therefore, we compare the condition distance \(\leq R\) by squaring both sides:

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

Since both sides are non-negative, this is equivalent to:

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

This allows us to determine the result exactly using only integer arithmetic, without any floating-point operations.

• Since we simply check each firework in \(O(1)\), the overall complexity is \(O(N)\), which is fast enough for \(N \leq 10^5\). No special algorithm is needed.

Algorithm

1. Read \(N\) and \(R\), and precompute \(R^2\).
2. For each firework \(i\), do the following:
   • Compute \(dx = X_i - P_i\) and \(dy = Y_i - Q_i\).
   • If \(dx^2 + dy^2 \leq R^2\), increment the count by \(1\).
3. Output the final count.

Concrete example: For \(R = 5\), Takahashi at \((1, 2)\), Aoki at \((4, 6)\):

• \(dx = 1 - 4 = -3\), \(dy = 2 - 6 = -4\)
• \(dx^2 + dy^2 = 9 + 16 = 25\)
• \(R^2 = 25\)
• Since \(25 \leq 25\), they are judged to have “watched together” (distance exactly \(5\))

Complexity

• Time complexity: \(O(N)\) — constant-time computation for each firework
• Space complexity: \(O(N)\) — for storing input data (can be reduced to \(O(1)\) by reading input incrementally)

Implementation Notes

• Do not use square roots: Using sqrt may cause misjudgment due to floating-point errors. The standard technique is to square both sides and compare using integers.

• Beware of overflow: Since coordinate values can be up to \(10^9\), \(dx\) can be up to \(2 \times 10^9\), and \(dx^2\) can be up to \(4 \times 10^{18}\). In C++ and similar languages, 64-bit integers (long long) are required. In Python, this is not an issue since arbitrary-precision integers are supported by default.

• Fast input: Since \(N\) can be up to \(10^5\), in Python we speed up input by reading all at once using sys.stdin.buffer.read().

  Source Code

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

This editorial was generated by claude4.6opus-thinking.