結果
問題 | No.2612 Close the Distance |
ユーザー |
![]() |
提出日時 | 2024-01-19 22:01:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 832 ms / 3,000 ms |
コード長 | 2,549 bytes |
コンパイル時間 | 2,024 ms |
コンパイル使用メモリ | 205,044 KB |
最終ジャッジ日時 | 2025-02-18 21:01:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
// https://atcoder.jp/contests/xmascon19/tasks/xmascon19_f #include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005; const ll INF=1LL<<34; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int N;cin>>N; vector<pair<ll,ll>> S(N); for(int i=0;i<N;i++){ ll a,b;cin>>a>>b; S[i]=mp(a+b,a-b); } sort(all(S)); auto solve=[&](vector<pair<ll,ll>> X,int type,ll len){ if(si(X)==0) return X; ll miH=INF,maH=-INF,miW=INF,maW=-INF; for(auto [a,b]:X){ chmin(miH,a); chmax(maH,a); chmin(miW,b); chmax(maW,b); } vector<pair<ll,ll>> res; ll U,D,L,R; if(type==0){ U=miH; D=miH+len; L=miW; R=miW+len; } if(type==1){ U=miH; D=miH+len; L=maW-len; R=maW; } if(type==2){ U=maH-len; D=maH; L=miW; R=miW+len; } if(type==3){ U=maH-len; D=maH; L=maW-len; R=maW; } for(auto [a,b]:X){ if(U<=a&&a<=D&&L<=b&&b<=R){ }else{ res.push_back(mp(a,b)); } } return res; }; ll left=-1,right=1LL<<33; while(right-left>1){ ll mid=(left+right)/2; bool f=false; for(int a=0;a<4;a++){ auto T1=S; auto T2=solve(T1,a,mid); if(si(T1)==si(T2)) continue; if(si(T2)==0) f=true; for(int b=0;b<4;b++){ auto T3=solve(T2,b,mid); if(si(T2)==si(T3)) continue; if(si(T3)==0) f=true; for(int c=0;c<4;c++){ auto T4=solve(T3,c,mid); if(si(T4)==0) f=true; if(f) break; } if(f) break; } if(f) break; } if(f) right=mid; else left=mid; } cout<<right<<endl; }