概要

各花火について、高橋君のいる位置からの距離が \(R\) 以下かどうかを判定し、見える花火の満足度 \(P_i\) を合計する問題です。
全ての花火を 1 回ずつ調べればよいので、素直に判定していけば解けます。

考察

花火 \(i\) の打ち上げ地点が \((X_i, Y_i)\)、高橋君の位置が \((X_A, Y_A)\) なので、2 点間のユークリッド距離は

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

です。
この距離が \(R\) 以下なら、その花火は観覧できます。

ここで、そのまま毎回平方根を計算しても判定はできますが、実装では次の形に変形するのが定番です。

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

は、両辺とも非負なので平方して

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

と同値です。

この形にすると、

• 平方根を計算しなくてよい
• 浮動小数点誤差を避けられる
• 整数だけで安全に判定できる

という利点があります。

また、\(N \le 2 \times 10^5\) なので、各花火を 1 回ずつ見て判定する \(O(N)\) の方法で十分間に合います。
逆に、複雑なデータ構造や探索は不要です。

例えば、高橋君が \((0, 0)\)、\(R = 5\) のとき、

• 花火が \((3, 4)\) にあるなら、距離の二乗は \(3^2 + 4^2 = 25\)
• \(R^2 = 25\)

なので \(25 \le 25\) となり、この花火は観覧できます。

アルゴリズム

1. \(R^2\) をあらかじめ計算しておく。
2. 各花火について、
   
   • \(dx = X_i - X_A\)
   • \(dy = Y_i - Y_A\) を求める。
3. \(dx^2 + dy^2 \le R^2\) なら、その花火は観覧できるので満足度 \(P_i\) を答えに加算する。
4. 全ての花火を見終わったら、合計を出力する。

計算量

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

実装のポイント

• 距離の比較に平方根 sqrt を使わず、距離の二乗同士を比較するのがポイントです。

• 座標や半径は最大で \(10^9\) なので、二乗すると \(10^{18}\) 程度になります。Python では整数が自動で大きな値にも対応できるので安心です。

• 入力が多いため、sys.stdin.readline を使うと高速に読み込めます。

  ソースコード

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

---

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