No.180 美しいWhitespace (2)

三分探索を使う問題。三分探索は初めて書いた。double の三分探索でWAくらったりしたが、long long で三分探索して AC。
inf = (1<<30) じゃ足りなかったりした。
二分探索でもできるらしい。
極値は線分の交点上でとるはずなんで、うまく必要な交点だけ計算して O(N^2) で計算するって手もあるみたい。

class BeautifulWhitespace2 {
public:
    void solve(void)
    {
        int N;
        cin>>N;

        vector<ll> a(N);
        vector<ll> b(N);

        REP(i,N) cin>>a[i]>>b[i];

        //
        //
        //              /        |
        //     ---     /        |
        //  ---       /        |
        //
        // のような傾きの異なる 3 直線とすると
        // max(a[i]+b[i]*x) は領域 A 側にもっとも近い線分
        // min(a[i]+b[i]*x) は領域 B 側にもっとも近い線分
        //
        //        |/
        // A      /
        //       /|
        //      /|-------
        // ----/-
        //    / |    B
        //
        // によって構成される。また max(...) >= min(...) なので
        // 差は必ず 0 以上となる。よって f(x) は極値を 1 つもつ凹関数となる。
        // 三分探索をすればよい。

        const ll inf = (1LL<<60);

        // O(N)
        auto f = [=](ll x) {
            if (x <= 0)
                return inf;

            ll maxF = a[0]+b[0]*x;
            ll minF = a[0]+b[0]*x;

            FOR(i,1,N)
            {
                minF = min(minF, a[i]+b[i]*x);
                maxF = max(maxF, a[i]+b[i]*x);
            }
            return maxF - minF;
        };

        const int maxLoop = 1000;
        ll left = 1;
        ll right = (1<<30);

        // O(N*1000)
        for (int loop = 0; loop < maxLoop; ++loop)
        {
            if ( left == right )
                break;
            //
            // l ---u---v--- r
            //
            ll u = (left*2 + right)/3;
            ll v = (left + right*2)/3;

            if ( f(u) > f(v) )
                left = u;
            else
                right = v;
        }
        ll x = (left+right)/2;
        cout<<x<<endl;
    }
};