結果

問題 No.2612 Close the Distance
コンテスト
ユーザー Yifan Kang
提出日時 2024-06-13 17:58:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,780 bytes
コンパイル時間 2,374 ms
コンパイル使用メモリ 172,404 KB
実行使用メモリ 16,720 KB
最終ジャッジ日時 2024-06-13 17:58:39
合計ジャッジ時間 13,338 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

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;
    }
    int L = 0,R = 2e9;
    while(L < R){
        int mid = (L + R) / 2;
        if(chk(mid))R = mid;
        else L = mid + 1;
    }
    cout << L << endl;
    return 0;
}
0