解法

概要

凸性により三分探索。

メモ

整理すると「一次関数 と区間 が与えられるので を求めよ」という問題になる。 凸性をもっと上手く使った賢いがありそうに思えるが二分探索しか思い付かなくて気持ち悪い。

実装

#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;
}