Overview

Given Takahashi’s current position \((X_A, Y_A)\), the task is to identify all firework launch sites within a distance of radius \(R\), and compute the sum of their satisfaction values \(P_i\).

Analysis

The core of this problem lies in how to accurately and efficiently determine whether the distance between two points is at most \(R\).

1. Distance Comparison Method

The Euclidean distance between two points \((X_A, Y_A)\) and \((X_i, Y_i)\) is given by the following formula: $\(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2}\)\( The condition is that "this distance is at most \)R\(," which can be written as: \)\(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2} \leq R\)$

However, computing this directly requires the use of a “square root.” In programming, floating-point (decimal) arithmetic inherently involves precision errors, and when the distance is very close to \(R\), the comparison may yield an incorrect result.

To avoid this, we can square both sides and compare using only integers: $\((X_i - X_A)^2 + (Y_i - Y_A)^2 \leq R^2\)$ Using this formula, we can make accurate comparisons without worrying about precision errors.

2. Complexity and Constraint Verification

The number of fireworks \(N\) is at most \(2 \times 10^5\). Since the above computation for each firework takes \(O(1)\), the overall time complexity is \(O(N)\). This is sufficiently fast for the typical competitive programming time limit (around 2 seconds).

Algorithm

1. Read Takahashi’s coordinates \((X_A, Y_A)\), the radius \(R\), and each firework’s information \((X_i, Y_i, P_i)\) from the input.
2. Precompute the square of the radius \(R^2\) as the comparison threshold.
3. Initialize a variable total_satisfaction to \(0\) to hold the cumulative satisfaction.
4. For each firework, repeat the following:
   • Compute the difference in the \(X\) direction: \(dx = X_i - X_A\).
   • Compute the difference in the \(Y\) direction: \(dy = Y_i - Y_A\).
   • Compute the squared distance: \(dist\_sq = dx^2 + dy^2\).
   • If \(dist\_sq \leq R^2\), add \(P_i\) to total_satisfaction.
5. Output the final total_satisfaction.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan through the \(N\) fireworks exactly once, the runtime is proportional to the input size.
• Space complexity: \(O(N)\)
  • If all input is read at once, storing it in a list requires \(O(N)\) memory.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Handling large integers: The square of the coordinate differences can be as large as \((2 \times 10^9)^2 = 4 \times 10^{18}\). Python natively supports arbitrary-precision integers, so there is no need to worry about overflow.

• Maintaining precision: As discussed in the analysis, using “squared comparison” instead of math.sqrt is the standard technique for making accurate comparisons.

  Source Code

import sys

def solve():
    # 競技プログラミングにおける高速な入力読み込み
    # 全ての入力を一度に読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての文字列を整数に一括変換します
    # map(int, ...) は非常に高速です
    data = list(map(int, input_data))
    
    # 最初の4つの値（N, XA, YA, R）を取得します
    N = data[0]
    XA = data[1]
    YA = data[2]
    R = data[3]
    
    # ユークリッド距離の公式 √(dx^2 + dy^2) <= R を、
    # 計算速度と精度のために両辺を2乗した dx^2 + dy^2 <= R^2 で判定します
    R_sq = R * R
    total_satisfaction = 0
    
    # 各花火の情報はインデックス4から3つずつ並んでいます
    # (Xi, Yi, Pi)
    for i in range(N):
        idx = 4 + 3 * i
        xi = data[idx]
        yi = data[idx + 1]
        pi = data[idx + 2]
        
        # 高橋君の座標からの相対距離の2乗を計算
        dx = xi - XA
        dy = yi - YA
        dist_sq = dx * dx + dy * dy
        
        # 距離の2乗が R^2 以下であれば観覧可能
        if dist_sq <= R_sq:
            total_satisfaction += pi
            
    # 結果を出力します
    sys.stdout.write(str(total_satisfaction) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.