結果

問題 No.2612 Close the Distance
ユーザー inksamuraiinksamurai
提出日時 2024-01-20 04:47:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 630 ms / 3,000 ms
コード長 2,207 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 208,896 KB
実行使用メモリ 18,028 KB
最終ジャッジ日時 2024-09-28 05:25:29
合計ジャッジ時間 12,108 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 302 ms
13,040 KB
testcase_07 AC 287 ms
13,072 KB
testcase_08 AC 291 ms
13,160 KB
testcase_09 AC 377 ms
13,108 KB
testcase_10 AC 306 ms
13,216 KB
testcase_11 AC 315 ms
13,080 KB
testcase_12 AC 304 ms
13,016 KB
testcase_13 AC 332 ms
13,116 KB
testcase_14 AC 325 ms
13,252 KB
testcase_15 AC 317 ms
13,108 KB
testcase_16 AC 467 ms
17,304 KB
testcase_17 AC 602 ms
16,636 KB
testcase_18 AC 608 ms
16,988 KB
testcase_19 AC 630 ms
16,344 KB
testcase_20 AC 460 ms
16,988 KB
testcase_21 AC 521 ms
16,744 KB
testcase_22 AC 502 ms
16,600 KB
testcase_23 AC 437 ms
17,284 KB
testcase_24 AC 551 ms
16,860 KB
testcase_25 AC 593 ms
18,028 KB
testcase_26 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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