結果

問題 No.2612 Close the Distance
ユーザー inksamuraiinksamurai
提出日時 2024-01-20 04:47:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 647 ms / 3,000 ms
コード長 2,207 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 199,344 KB
最終ジャッジ日時 2025-02-18 21:47:28
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _48SMghu ios::sync_with_stdio(0),cin.tie(0)
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

const int o=1e9;

const int o2=o*2;

void slv(){
	int n;
	cin>>n;
	vec(pii) a(n);
	rep(i,n){
		cin>>a[i].fi>>a[i].se;
	}
	vec(pii) pts;
	for(auto [x,y]:a){
		pts.pb({x-y,x+y});
	}

	auto fa=[&](vec(pii) pts,int d){
		int mi_x=o2,ma_x=-o2,mi_y=o2,ma_y=-o2;
		for(auto [x,y]:pts){
			mi_x=min(mi_x,x);
			ma_x=max(ma_x,x);
			mi_y=min(mi_y,y);
			ma_y=max(ma_y,y);
		}
		rep(i,2){
			int l_x,r_x;
			if(!i){
				l_x=mi_x,r_x=mi_x+d;
			}else{
				l_x=ma_x-d,r_x=ma_x;
			}
			rep(j,2){
				int l_y,r_y;
				if(!j){
					l_y=mi_y,r_y=mi_y+d;
				}else{
					l_y=ma_y-d,r_y=ma_y;
				}
				int mi_x1=o2,ma_x1=-o2,mi_y1=o2,ma_y1=-o2;
				for(auto [x,y]:pts){
					if(l_x<=x and x<=r_x and l_y<=y and y<=r_y) continue;
					mi_x1=min(mi_x1,x);
					ma_x1=max(ma_x1,x);
					mi_y1=min(mi_y1,y);
					ma_y1=max(ma_y1,y);
				}
				if(ma_x1-mi_x1<=d and ma_y1-mi_y1<=d){
					return 1;
				}
			}
		}
		return 0;
	};

	auto af=[&](int d){
		int mi_x=o2,ma_x=-o2,mi_y=o2,ma_y=-o2;
		for(auto [x,y]:pts){
			mi_x=min(mi_x,x);
			ma_x=max(ma_x,x);
			mi_y=min(mi_y,y);
			ma_y=max(ma_y,y);
		}
		rep(i,2){
			int l_x,r_x;
			if(!i){
				l_x=mi_x,r_x=mi_x+d;
			}else{
				l_x=ma_x-d,r_x=ma_x;
			}
			rep(j,2){
				int l_y,r_y;
				if(!j){
					l_y=mi_y,r_y=mi_y+d;
				}else{
					l_y=ma_y-d,r_y=ma_y;
				}
				vec(pii) npts;
				for(auto [x,y]:pts){
					if(l_x<=x and x<=r_x and l_y<=y and y<=r_y) continue;
					npts.pb({x,y});
				}
				int e=fa(npts,d);
				if(e){
					return 1;
				}
			}
		}
		return 0;
	};

	int l=0,r=o2;
	int opt=r;
	while(l<=r){
		int m=(l+r)/2;
		if(af(m)){
			opt=m,r=m-1;
		}else{
			l=m+1;
		}
	}
	print(opt);
}

signed main(){
_48SMghu;
	slv();
}
0