Overview

For each firework, calculate the distance between Takahashi and Aoki, and count the number of fireworks where the distance is at most \(R\). Sum up the count across all \(N\) fireworks and output the result.

Analysis

The distance between the two people at the \(i\)-th firework is
\(\sqrt{(X_i-P_i)^2 + (Y_i-Q_i)^2}\). We want to determine whether this is at most \(R\), but computing the square root each time can be slow and may introduce precision errors.

The key insight here is that “we can compare without taking the square root.”
The condition that the distance is at most \(R\): \(\sqrt{(X_i-P_i)^2 + (Y_i-Q_i)^2} \le R\) can be squared on both sides (since both sides are non-negative, this is equivalent): \((X_i-P_i)^2 + (Y_i-Q_i)^2 \le R^2\)

In this form, the check only requires integer arithmetic, which is error-free and fast.
Since \(N \le 10^5\), a straightforward \(O(N)\) approach that processes each firework once is more than sufficient (there is no need to check pairs of fireworks in \(O(N^2)\), which would certainly result in TLE).

Example: If \(R=5\) and the differences are \((dx,dy)=(3,4)\), then \(dx^2+dy^2=9+16=25 \le 25\), so they “watched it together.”

Algorithm

1. Precompute \(R^2\) from the input.
2. For each firework \(i=1..N\):
   • Compute \(dx=X_i-P_i\), \(dy=Y_i-Q_i\)
   • If \(dx^2+dy^2 \le R^2\), increment the answer by 1
3. Output the total.

Complexity

• Time complexity: \(O(N)\) (constant number of operations per firework)
• Space complexity: \(O(1)\) (process input on the fly without additional arrays)

Implementation Notes

• Do not use square root (sqrt); instead compare \(R^2\) with \(dx^2+dy^2\).

• Coordinates and \(R\) can be up to \(10^9\), so their squares can reach up to about \(10^{18}\). Python integers do not overflow, so this is safe (in other languages, use 64-bit integers).

• Since the input can be large, using fast input methods like sys.stdin.buffer.read().split() helps ensure stability.

  Source Code

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

This editorial was generated by gpt-5.2-high.