解法

概要

凸性により三分探索。\(O(N \log N)\)。

メモ

整理すると「一次関数 \(f_0, f_1, \dots, f _ {2N - 1}\) と区間 \([l, r) \subseteq \mathbb{R}\) が与えられるので \(\arg\min _ {x \in [l, r)} \max \{ f_i(x) \mid i \lt 2N \}\) を求めよ」という問題になる。 凸性をもっと上手く使った賢い\(O(N)\)がありそうに思えるが二分探索しか思い付かなくて気持ち悪い。

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }

/**
 * @arg f must be a downward-convex function
 * @retrun argmin f
 * @note f is called (iteration + 1) times
 */
template <class Function>
double golden_section_search(double l, double r, int iteration, Function f) {
    static const double GOLDEN_RATIO = (1 + sqrt(5)) / 2;
    double m1 = l + (r - l) / (GOLDEN_RATIO + 1);
    double m2 = l + (r - l) / GOLDEN_RATIO;  // NOTE: this equals to GOLDEN_RATIO / (GOLDEN_RATIO + 1.0)
    double f1 = f(m1);
    double f2 = f(m2);
    while (iteration --) {
        if (f1 < f2){
            r = m2;
            m2 = m1;
            f2 = f1;
            m1 = l + (r - l) / (GOLDEN_RATIO + 1);
            f1 = f(m1);
        } else {
            l = m1;
            m1 = m2;
            f1 = f2;
            m2 = l + (r - l) / GOLDEN_RATIO;
            f2 = f(m2);
        }
    }
    return (l + r) / 2;
}

double solve(int n, vector<int> const & x, vector<int> const & w) {
    double l = *min_element(ALL(x));
    double r = *max_element(ALL(x));
    return golden_section_search(l, r, 100, [&](double p) {
        double acc = - INFINITY;
        REP (i, n) chmax(acc, abs(x[i] - p) * w[i]);
        return acc;
    });
}

int main() {
    int n; cin >> n;
    vector<int> x(n), w(n);
    REP (i, n) cin >> x[i] >> w[i];
    cout << setprecision(16) << solve(n, x, w) << endl;
    return 0;
}