結果
問題 | No.2612 Close the Distance |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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(); }