結果

問題 No.180 美しいWhitespace (2)
コンテスト
ユーザー codershifth
提出日時 2016-01-27 01:16:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 2,406 bytes
コンパイル時間 1,470 ms
コンパイル使用メモリ 163,180 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 17:38:48
合計ジャッジ時間 2,465 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


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;

        // 前後 1 つ分くらいは調べてみる
        auto xs = vector<ll> {x-1, x, x+1};
        cout<<*min_element(RANGE(xs), [=](ll a,ll b){return f(a)<f(b);})<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new BeautifulWhitespace2();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0