結果

問題 No.2612 Close the Distance
ユーザー Yifan KangYifan Kang
提出日時 2024-06-13 18:00:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 811 ms / 3,000 ms
コード長 1,787 bytes
コンパイル時間 2,500 ms
コンパイル使用メモリ 207,236 KB
実行使用メモリ 9,432 KB
最終ジャッジ日時 2024-06-13 18:00:48
合計ジャッジ時間 15,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 373 ms
8,088 KB
testcase_07 AC 423 ms
8,092 KB
testcase_08 AC 325 ms
8,088 KB
testcase_09 AC 322 ms
8,088 KB
testcase_10 AC 371 ms
8,092 KB
testcase_11 AC 320 ms
8,092 KB
testcase_12 AC 368 ms
8,092 KB
testcase_13 AC 292 ms
8,088 KB
testcase_14 AC 294 ms
8,088 KB
testcase_15 AC 305 ms
8,084 KB
testcase_16 AC 675 ms
9,304 KB
testcase_17 AC 596 ms
9,424 KB
testcase_18 AC 657 ms
9,308 KB
testcase_19 AC 653 ms
9,300 KB
testcase_20 AC 811 ms
9,304 KB
testcase_21 AC 649 ms
9,304 KB
testcase_22 AC 803 ms
9,428 KB
testcase_23 AC 769 ms
9,304 KB
testcase_24 AC 738 ms
9,432 KB
testcase_25 AC 650 ms
9,432 KB
testcase_26 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 2e5 + 5;
const ll inf = 1e14;
int n;
vector <ll> X,Y;
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
bool solve(ll A,int k,const vi &p){
    if(!p.size())return 1;
    if(k == 0)return 0;
    ll xs[2] = {-inf,inf},ys[2] = {-inf,inf};
    for(int i : p){//the min/max of the upper right corner of the square
        chmax(xs[0],X[i]),chmax(ys[0],Y[i]);
        chmin(xs[1],X[i] + A),chmin(ys[1],Y[i] + A);
    }
    if(k == 1){
        return (xs[0] <= xs[1] && ys[0] <= ys[1]);
    }
    rep(a,0,1)rep(b,0,1){
        vi nxt;
        //we cover one corner with the square
        for(int i : p){
            if(xs[a] >= X[i] && X[i] >= xs[a] - A && 
            ys[b] >= Y[i] && Y[i] >= ys[b] - A);
            else nxt.pb(i);
        }
        if(solve(A,k - 1,nxt))return 1;
    }
    return 0;
}
bool chk(ll A){
    vi p(n);
    rep(i,0,n - 1)p[i] = i;
    return solve(A,3,p);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    X.resize(n),Y.resize(n);
    rep(i,0,n - 1){
        int a,b;
        cin >> a >> b;
        //Manhattan distance to Chebyshev
        X[i] = a + b,Y[i] = a - b;
    }
    ll lo = -1, hi = 2001001001LL;
    for (; lo + 1 < hi; ) {
      const ll mid = (lo + hi) / 2;
      (chk(mid) ? hi : lo) = mid;
    }
    cout << hi << endl;
    return 0;
}
0