概要

各花火について「高橋君の位置からの距離が半径 \(R\) 以内か」を判定し、条件を満たす花火の満足度 \(P_i\) を合計する問題です。
全花火を1回ずつ調べれば解けます。

考察

重要な観察は、各花火の判定が独立していることです。
つまり「ある花火が見えるかどうか」は、その花火の座標と高橋君の座標だけで決まり、他の花火の情報は不要です。

花火 \((X_i, Y_i)\) と高橋君 \((X_A, Y_A)\) のユークリッド距離は

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

です。これが \(R\) 以下なら見えます。

ここで素朴に毎回平方根を計算しても正しくは解けますが、次の理由で非効率・不安定になりやすいです。

• 平方根計算は比較的重い
• 浮動小数点誤差で境界（ちょうど距離 \(R\)）の判定が不安になる

そこで、大小比較だけなら平方根は不要です。
次の同値変形を使います：

\( \sqrt{d^2} \le R \iff d^2 \le R^2 \)

つまり、

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

を整数のまま判定すればOKです。
これで高速かつ安全に判定できます。

アルゴリズム

1. 入力で \(N, X_A, Y_A, R\) を受け取る。
2. \(r2 = R^2\) を前計算する。
3. 合計値 total を 0 で初期化。
4. 各花火について：
   • \(dx = X_i - X_A\), \(dy = Y_i - Y_A\) を計算
   • \(dx^2 + dy^2 \le r2\) なら total += P_i
5. 最後に total を出力。

具体例：
\(R=5\) のとき \(R^2=25\)。
ある花火について \(dx=3, dy=4\) なら \(dx^2+dy^2=9+16=25\) なので「見える」と判定できます（境界含む）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 距離判定は平方根を使わず、二乗同士で比較する。

• 条件は「以下」なので <= を使う（境界上の花火も観覧可能）。

• 座標差や二乗は大きくなる可能性がありますが、Python の整数は多倍長なのでそのまま安全に扱えます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    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)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。