// g++-13 3.cpp -std=c++17 -O2 -I . #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; #include using namespace atcoder; using ll = long long; using ld = long double; using vi = vector; using vvi = vector; using vll = vector; using vvll = vector; using vld = vector; using vvld = vector; using vst = vector; using vvst = vector; #define fi first #define se second #define pb push_back #define eb emplace_back #define pq_big(T) priority_queue,less> #define pq_small(T) priority_queue,greater> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) #define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end()) // https://nachiavivias.github.io/cp-library/cpp/multi-dimensional/two-d-rectangle-query.html // https://github.com/NachiaVivias/cp-library/blob/main/Cpp/Include/nachia/multi-dimensional/two-d-rectangle-query.hpp // https://judge.yosupo.jp/submission/139718 // https://atcoder.jp/contests/arc159/submissions/41442160 // T 座標の型 // S 点に乗せる型 // op 演算 // e 単位元 // 交換則,結合則は必要 template< typename T, typename S, S (*op)(S, S), S (*e)() > struct rectanglequery{ private: struct BitVectorRank { using u64 = std::uint64_t; using u32 = std::uint32_t; static u32 popcountll(u64 c){ #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/255)) >> 56; return c; #endif } std::vector> a; BitVectorRank(const std::vector& b = {}){ int n = b.size(); a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0)); auto p = b.begin(); u32 sum = 0; u64 tmp = 0; for(int i=0; i<=n; i+=64){ tmp = 0; int maxd = std::min(n - i, 64); for(int d=0; d> 6]; return (u32)(popcountll(b & ~(~u64(0) << (i & 63)))) + s; } bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; } }; struct BIT{ vi A; BIT(int n=0){ A.assign(n+1,0); } int sum(int r){ int res = 0; while(r){ res += A[r]; r -= r & -r; } return res; } void add(int p, int x){ p += 1; while(p < A.size()){ A[p] += x; p += p & -p; } } }; struct segmenttree{ int _n; std::vector node; segmenttree() = default; segmenttree(int n){ _n=1; while(_n &v){ int n=v.size(); _n=1; while(_n1){ i>>=1; node[i]=op(node[2*i],node[2*i+1]); } } // [i] <- op([i],val) void update(int i,S val){ i+=_n; node[i]=op(node[i],val); while(i>1){ i>>=1; node[i]=op(node[2*i],node[2*i+1]); } } S get(int i){ i+=_n; return node[i]; } S prod(int l,int r){ S pdl=e(),pdr=e(); l+=_n;r+=_n; while(l>=1;r>>=1; } return op(pdl,pdr); }; }; int n; int N; int logN; std::vector Xsorted; std::vector Ysorted; std::vector rankX; std::vector> Idx; std::vector Z; std::vector L; std::vector seg; std::map,int> index; public: rectanglequery(const std::vector> &points){ n=points.size(); for(int i=0;i sortIY(n); for(int i=0;i sortIX(n); rankX.resize(n); for(int i=0;i(n,-1)); L.resize(logN); Z.resize(logN); for(int i=0;i=0;i--){ std::vector Lbuf(n,0); auto& preList = Idx[i+1]; int z=((n>>(i+1))< get_update_points(int v) const { std::vector res(logN+1); int p = rankX[v]; int d = logN; while(d > 0){ res[d] = { d,p }; d--; if(L[d].get(p)) p = L[d].rank(p); else p = Z[d] + p - L[d].rank(p); } res[d] = {d,p}; return res; } struct Query{ int d,l,r; }; std::vector get_ranges_from_idx(int xl, int xr, int yl, int yr){ std::vector res; struct Search{ int i, xa, xb, ys, yt; }; std::vector Q; res.reserve((logN+1)*2); Q.reserve((logN+1)*2); Q.push_back({ logN,0,n,yl,yr }); for(int i=0; i<(int)Q.size(); i++){ auto p = Q[i]; if(p.xa == p.xb) continue; if(xr <= p.xa || p.xb <= xl) continue; if(xl <= p.xa && p.xb <= xr){ res.push_back({ p.i, p.ys, p.yt }); continue; } p.i--; int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt); Q.push_back({ p.i,p.xa,p.xa+(1< get_ranges(T xl, T xr, T yl, T yr){ return get_ranges_from_idx( lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(), lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(), lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(), lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin() ); } ////// // point <- val void point_set(T px,T py,S val){ int ind=index[{px,py}]; for(auto qq:this->get_update_points(ind)){ seg[qq.d].add(qq.i,val); } } // point <- op(point,val) void point_update(T px,T py,S val){ int ind=index[{px,py}]; for(auto qq:this->get_update_points(ind)){ seg[qq.d].add(qq.i,val); } } S query(T x_mn,T x_mx,T y_mn,T y_mx){ S res=e(); for(auto qq:this->get_ranges(x_mn,x_mx,y_mn,y_mx)){ res=op(res,seg[qq.d].sum(qq.r)-seg[qq.d].sum(qq.l)); } return res; } }; int op(int a,int b){ return a+b; } int e(){ return (int)0; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); auto start=clock(); int n;cin>>n; vector> points(n); rep(i,0,n){ int x,y;cin>>x>>y; points[i]={x+y,x-y}; } rectanglequery rec(points); int ans=4e6; rep(i,0,n){ auto [x,y]=points[i]; rec.point_set(x,y,1); } rep(i,0,n){ auto [x,y]=points[i]; int ng1=0,ok1=4e5+10; int ok2_init=1e7,ng2_init=-1; while(ok1-ng1>1){ int c=(ok1+ng1)/2; int q=rec.query(x-c,x+c+1,y-c,y+c+1); if(q==1){ ng1=c; } else{ ok1=c; if(q==n){ ok2_init=min(ok2_init,c); } else{ ng2_init=max(ng2_init,n); } } } if(rec.query(x-(ok1+ans),x+(ok1+ans+1),y-(ok1+ans),y+(ok1+ans+1))!=n){ continue; } int ok2=min(ok1+ans,ok2_init),ng2=max(ok1,ng2_init); while(ok2-ng2>1){ int c=(ok2+ng2)/2; int q=rec.query(x-c,x+c+1,y-c,y+c+1); if(q==n){ ok2=c; } else{ ng2=c; } } ans=min(ans,ok2-ok1); } cout<