結果

問題 No.2612 Close the Distance
ユーザー Yifan Kang
提出日時 2024-06-13 18:00:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 689 ms / 3,000 ms
コード長 1,787 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 198,448 KB
最終ジャッジ日時 2025-02-21 21:30:54
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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