概要

数直線上に配置された \(N\) 台のスピーカーから測定点 \(P\) に届く音の強さの総和を求める問題です。

考察

問題文の通り、\(i\) 番目のスピーカーの音が測定点に届くときの強さは \(\frac{V_i}{|X_i - P|}\) と表されます。測定点と同じ座標にスピーカーがある場合（\(X_i = P\)）はゼロ除算が発生してしまうため、計算から除外する必要があります。

特別な工夫や高度なアルゴリズムは不要で、各スピーカーについて順番に条件を確認し、合計を計算していく素朴なアプローチで十分です。制約から \(N \leq 2 \times 10^5\) であるため、1台ずつ処理する \(O(N)\) の計算で十分に実行時間内に終わります。

アルゴリズム

1. スピーカーの台数 \(N\) と測定点の座標 \(P\) を入力します。
2. 合計を保持する変数（浮動小数点数型）を \(0\) で初期化します。
3. 各スピーカーの座標 \(X_i\) と出力の強さ \(V_i\) を入力し、以下の処理を行います。
   • もし \(X_i \neq P\) であれば、距離 \(d = |X_i - P|\) を計算します。
   • \(\frac{V_i}{d}\) を合計変数に加算します。
   • もし \(X_i = P\) であれば、何も行いません（除外）。
4. 最後に、合計を出力します。許容誤差が \(10^{-4}\) なので、小数点以下の桁数を十分に確保して出力します。

計算量

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

実装のポイント

• 座標 \(P\) や \(X_i\) は \(-10^9\) 以上 \(10^9\) 以下の整数であり、差分 \(|X_i - P|\) も最大で \(2 \times 10^9\) になります。そのため、32ビット整数型（int）ではなく64ビット整数型（long long）を使用する必要があります。

• 割り算を行う際、整数同士の割り算にならないように、割られる数または割る数を浮動小数点数（double）にキャストします。

• 出力時は、要求される精度（絶対誤差 \(10^{-4}\) 以下）を満たすために、小数点以下の桁数を多めに指定して出力すると安全です。

  ソースコード

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long P;
    if (!(cin >> N >> P)) return 0;
    
    double ans = 0.0;
    for (int i = 0; i < N; i++) {
        long long X, V;
        cin >> X >> V;
        if (X != P) {
            long long dist = (X > P) ? (X - P) : (P - X);
            ans += static_cast<double>(V) / dist;
        }
    }
    
    cout << fixed << setprecision(10) << ans << "\n";
    return 0;
}

この解説は or-glm-5.2-high によって生成されました。