据说可以用线段树做但是我不会，只能写一个 KD-Tree 了

对于每个点求出距离它最远的点和最近的点的距离，然后取 min 即可

因为这个东西是可以剪枝的，所以跑的挺快的

#include 
    
     #define For(i, a, b) for(int i = a; i <= b; i++)using namespace std;typedef unsigned long long ull;typedef long long ll;template 
     
      inline void read(_T &f) {    f = 0; _T fu = 1; char c = getchar();    while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();}    while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}    f *= fu;}const int N = 1e5 + 5;int WD, siz, n, root;struct po {    int a[2];    bool operator < (const po A) const {return a[WD] < A.a[WD];}}t[N];struct Node {    int mn[2], mx[2], lc, rc;    po tp;}p[N];void update(int u) {    int l = p[u].lc, r = p[u].rc;    for(register int i = 0; i <= 1; i++) {        p[u].mn[i] = p[u].mx[i] = p[u].tp.a[i];        if(l) p[u].mn[i] = min(p[u].mn[i], p[l].mn[i]), p[u].mx[i] = max(p[u].mx[i], p[l].mx[i]);        if(r) p[u].mn[i] = min(p[u].mn[i], p[r].mn[i]), p[u].mx[i] = max(p[u].mx[i], p[r].mx[i]);    }}int build(int l, int r, int wd) {    if(l > r) return 0;    int u = ++siz, mid = (l + r) >> 1;    WD = wd; nth_element(t + l, t + mid, t + r + 1);    p[u].tp = t[mid]; p[u].lc = build(l, mid - 1, wd ^ 1); p[u].rc = build(mid + 1, r, wd ^ 1);    update(u); return u;}// 最小距离 int calc1(int u, po tp) {    int ans = 0;    for(register int i = 0; i <= 1; i++) ans += max(0, p[u].mn[i] - tp.a[i]) + max(0, tp.a[i] - p[u].mx[i]);    return ans;}int calc2(int u, po tp) {    int ans = 0;    for(register int i = 0; i <= 1; i++) ans += max(abs(tp.a[i] - p[u].mn[i]), abs(tp.a[i] - p[u].mx[i]));    return ans;}int dis(po a, po b) {    int ans = 0;    for(register int i = 0; i <= 1; i++) ans += abs(a.a[i] - b.a[i]);    return ans;}const int INF = 0x7f7f7f7f;int ans1, ans2;void query1(int u, po tp) {    if(!u) return;    int now = dis(p[u].tp, tp);    if(ans1 > now && now) ans1 = now;    int l = INF, r = INF;    if(p[u].lc) l = calc1(p[u].lc, tp);    if(p[u].rc) r = calc1(p[u].rc, tp);    if(l < r) {        if(l < ans1) query1(p[u].lc, tp);        if(r < ans1) query1(p[u].rc, tp);    } else {        if(r < ans1) query1(p[u].rc, tp);        if(l < ans1) query1(p[u].lc, tp);    }}void query2(int u, po tp) {    if(!u) return;    int now = dis(p[u].tp, tp);    if(ans2 < now) ans2 = now;    int l = -1, r = -1;    if(p[u].lc) l = calc2(p[u].lc, tp);    if(p[u].rc) r = calc2(p[u].rc, tp);    if(l > r) {        if(l > ans2) query2(p[u].lc, tp);        if(r > ans2) query2(p[u].rc, tp);    } else {        if(r > ans2) query2(p[u].rc, tp);        if(l > ans2) query2(p[u].lc, tp);    }}int minn = INF;int main() {    cin >> n;    for(register int i = 1; i <= n; i++) read(t[i].a[0]), read(t[i].a[1]);    root = build(1, n, 0);    for(register int i = 1; i <= n; i++) {        ans1 = INF, ans2 = -INF;        query1(root, t[i]);        query2(root, t[i]);        minn = min(minn, ans2 - ans1);    }    cout << minn << endl;    return 0;}