Overview

For each firework, determine whether the distance from Takahashi’s position is at most \(R\), and sum up the satisfaction values \(P_i\) of the visible fireworks. Since we only need to check each firework once, we can solve this by straightforwardly checking each one.

Analysis

The launch point of firework \(i\) is \((X_i, Y_i)\) and Takahashi’s position is \((X_A, Y_A)\), so the Euclidean distance between the two points is

\( \sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2} \)

If this distance is at most \(R\), then that firework can be viewed.

Here, while we could compute the square root each time and still make the determination, a standard technique in implementation is to transform the inequality as follows.

\( \sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2} \le R \)

Since both sides are non-negative, we can square both sides to get the equivalent condition:

\( (X_i - X_A)^2 + (Y_i - Y_A)^2 \le R^2 \)

This form has the following advantages:

• No need to compute square roots
• Avoids floating-point errors
• Can be safely determined using only integers

Also, since \(N \le 2 \times 10^5\), an \(O(N)\) approach that checks each firework once is more than fast enough. Conversely, no complex data structures or searches are needed.

For example, if Takahashi is at \((0, 0)\) and \(R = 5\):

• If a firework is at \((3, 4)\), the squared distance is \(3^2 + 4^2 = 25\)
• \(R^2 = 25\)

So \(25 \le 25\) holds, and this firework can be viewed.

Algorithm

1. Precompute \(R^2\).
2. For each firework, compute:
   • \(dx = X_i - X_A\)
   • \(dy = Y_i - Y_A\)
3. If \(dx^2 + dy^2 \le R^2\), then that firework can be viewed, so add its satisfaction value \(P_i\) to the answer.
4. After checking all fireworks, output the total.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• The key point is to compare squared distances instead of using sqrt for distance comparison.

• Coordinates and the radius can be up to \(10^9\), so squaring them can produce values on the order of \(10^{18}\). In Python, integers automatically handle arbitrarily large values, so there is no concern.

• Since the input can be large, using sys.stdin.readline allows for faster reading.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, XA, YA, R = map(int, input().split())
    rr = R * R
    ans = 0

    for _ in range(N):
        x, y, p = map(int, input().split())
        dx = x - XA
        dy = y - YA
        if dx * dx + dy * dy <= rr:
            ans += p

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.