Overview

This is a problem where we need to find the total satisfaction of fireworks that are within distance \(R\) from Takahashi’s position on a 2D plane.

Analysis

• We need to determine whether the Euclidean distance between Takahashi’s position \((X_A, Y_A)\) and each firework’s launch point \((X_i, Y_i)\) is at most \(R\).
• The Euclidean distance is defined as \(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2}\), but computing the square root can introduce floating-point errors.
• The key idea is to perform the distance comparison using squared values. Specifically,

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

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

\[(X_i - X_A)^2 + (Y_i - Y_A)^2 \leq R^2\]

This allows us to compare exactly using integers, completely avoiding floating-point errors.

• Since we only need to check each firework once, a straightforward \(O(N)\) approach that iterates through all \(N\) fireworks is sufficient.

Algorithm

1. Read \(N, X_A, Y_A, R\) from input and precompute \(R^2\).
2. Initialize the total satisfaction total to \(0\).
3. For each firework \(i\):
   • Compute \(dx = X_i - X_A\) and \(dy = Y_i - Y_A\).
   • If \(dx^2 + dy^2 \leq R^2\), the firework is viewable, so add \(P_i\) to total.
4. Output total.

Concrete example: If Takahashi is at \((0, 0)\) and \(R = 5\), then a firework at \((3, 4)\) gives \(3^2 + 4^2 = 25 \leq 25\), so it is viewable. A firework at \((4, 4)\) gives \(4^2 + 4^2 = 32 > 25\), so it is not viewable.

Complexity

• Time complexity: \(O(N)\) — constant-time distance check for each firework
• Space complexity: \(O(1)\) — there is no need to store all firework information; we can process them one at a time

Implementation Notes

• Do not use square roots: Using math.sqrt risks misjudging boundary cases due to floating-point errors. By comparing squared values, we can make exact judgments using only integer arithmetic.

• Watch out for overflow (in other languages): Since the coordinate range is \(-10^9 \leq X_i, Y_i \leq 10^9\), the squared difference can be as large as \((2 \times 10^9)^2 = 4 \times 10^{18}\). In C++ and similar languages, long long is required, but in Python this is not an issue since it handles arbitrary-precision integers.

  Source Code

N, XA, YA, R = map(int, input().split())
R2 = R * R
total = 0
for _ in range(N):
    x, y, p = map(int, input().split())
    dx = x - XA
    dy = y - YA
    if dx * dx + dy * dy <= R2:
        total += p
print(total)

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