概要

2次元平面上で、高橋君の位置から距離 \(R\) 以内にある花火の満足度の合計を求める問題です。

考察

• 高橋君の位置 \((X_A, Y_A)\) と各花火の打ち上げ地点 \((X_i, Y_i)\) とのユークリッド距離が \(R\) 以下かどうかを判定すればよいです。
• ユークリッド距離の定義は \(\sqrt{(X_i - X_A)^2 + (Y_i - Y_A)^2}\) ですが、平方根の計算は浮動小数点の誤差を生む可能性があります。
• そこで、距離の比較を 二乗のまま 行うのがポイントです。すなわち、

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

は両辺が非負なので、

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

と同値です。こうすれば整数のまま正確に比較でき、浮動小数点誤差を完全に回避できます。

• 各花火について1回ずつ判定すればよいので、\(N\) 個の花火を順に見る素朴な \(O(N)\) のアプローチで十分間に合います。

アルゴリズム

1. 入力から \(N, X_A, Y_A, R\) を読み取り、\(R^2\) を事前に計算しておく。
2. 満足度の合計 total を \(0\) で初期化する。
3. 各花火 \(i\) について：
   • \(dx = X_i - X_A\)、\(dy = Y_i - Y_A\) を計算する。
   • \(dx^2 + dy^2 \leq R^2\) なら、その花火は観覧可能なので total に \(P_i\) を加算する。
4. total を出力する。

具体例: 高橋君が \((0, 0)\)、\(R = 5\) のとき、花火が \((3, 4)\) にあれば \(3^2 + 4^2 = 25 \leq 25\) なので観覧可能。花火が \((4, 4)\) にあれば \(4^2 + 4^2 = 32 > 25\) なので観覧不可。

計算量

• 時間計算量: \(O(N)\) — 各花火について定数時間の距離判定を行う
• 空間計算量: \(O(1)\) — 花火の情報を保持する必要はなく、1つずつ処理すればよい

実装のポイント

• 平方根を使わない: math.sqrt を使うと浮動小数点誤差で境界上のケースを誤判定する恐れがあります。二乗同士で比較することで整数演算のみで正確に判定できます。

• オーバーフローに注意（他言語の場合）: 座標の範囲が \(-10^9 \leq X_i, Y_i \leq 10^9\) なので、差の二乗は最大 \((2 \times 10^9)^2 = 4 \times 10^{18}\) 程度になります。C++ などでは long long が必要ですが、Python は多倍長整数を扱えるので問題ありません。

  ソースコード

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)

この解説は claude4.6opus-thinking によって生成されました。