結果
問題 | No.2612 Close the Distance |
ユーザー | inksamurai |
提出日時 | 2024-01-20 04:47:09 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 672 ms / 3,000 ms |
コード長 | 2,207 bytes |
コンパイル時間 | 2,357 ms |
コンパイル使用メモリ | 208,948 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2024-01-20 04:47:24 |
合計ジャッジ時間 | 13,873 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 3 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 324 ms
13,564 KB |
testcase_07 | AC | 326 ms
13,564 KB |
testcase_08 | AC | 306 ms
13,564 KB |
testcase_09 | AC | 402 ms
13,564 KB |
testcase_10 | AC | 322 ms
13,564 KB |
testcase_11 | AC | 340 ms
13,564 KB |
testcase_12 | AC | 323 ms
13,564 KB |
testcase_13 | AC | 350 ms
13,564 KB |
testcase_14 | AC | 351 ms
13,564 KB |
testcase_15 | AC | 351 ms
13,564 KB |
testcase_16 | AC | 486 ms
17,536 KB |
testcase_17 | AC | 652 ms
17,536 KB |
testcase_18 | AC | 638 ms
17,536 KB |
testcase_19 | AC | 672 ms
17,536 KB |
testcase_20 | AC | 480 ms
17,536 KB |
testcase_21 | AC | 555 ms
17,536 KB |
testcase_22 | AC | 537 ms
17,536 KB |
testcase_23 | AC | 458 ms
17,536 KB |
testcase_24 | AC | 590 ms
17,536 KB |
testcase_25 | AC | 608 ms
17,536 KB |
testcase_26 | AC | 2 ms
6,676 KB |
ソースコード
#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(); }