大意：给定 $n$ 个点，请找出一个点，使得这个点与其它所有点的曼哈顿距离的最大值与最小值之差最小。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
const int inf = 2147483647;

int n, rt, ansx, ansy, ans = inf;
int g[maxn];

struct node {
	int ls, rs;
	int x[2], L[2], R[2];
} t[maxn];

#define mid ((l + r) >> 1)

struct KDT {
	void pushup(int o) {
		for(int i = 0; i <= 1; i++) {
			t[o].L[i] = t[o].R[i] = t[o].x[i];
			if(t[o].ls) {
				t[o].L[i] = min(t[o].L[i], t[t[o].ls].L[i]);
				t[o].R[i] = max(t[o].R[i], t[t[o].ls].R[i]);
			}
			if(t[o].rs) {
				t[o].L[i] = min(t[o].L[i], t[t[o].rs].L[i]);
				t[o].R[i] = max(t[o].R[i], t[t[o].rs].R[i]);
			}
		}
	}

	int build(int l, int r, int d) {
		nth_element(g+l, g+mid, g+r+1, [&](int a, int b) {
			return t[a].x[d] < t[b].x[d];
		}) ;
		int o = g[mid];
		if(l < mid) t[o].ls = build(l, mid-1, d^1);
		if(mid < r) t[o].rs = build(mid+1, r, d^1);
		pushup(o);
		return o;
	}

	int f(int x, int y, int lx, int ly, int rx, int ry) {
		return (x<lx ? lx-x : (x>rx ? x-rx : 0) + (y<ly ? ly-y : (y>ry ? y-ry : 0)));
	}

	void query1(int o, int x) {
		if(!o) return;
		if(f(t[x].x[0], t[x].x[1], t[o].L[0], t[o].L[1], t[o].R[0], t[o].R[1]) > ansx) return;
		if(t[o].x[0] != t[x].x[0] || t[o].x[1] != t[x].x[1]) 
			ansx = min(ansx, f(t[x].x[0], t[x].x[1], t[o].x[0], t[o].x[1], t[o].x[0], t[o].x[1]));
		int a = t[o].ls ? f(t[x].x[0], t[x].x[1], t[t[o].ls].L[0], t[t[o].ls].L[1], t[t[o].ls].R[0], t[t[o].ls].R[1]) : inf;
		int b = t[o].rs ? f(t[x].x[0], t[x].x[1], t[t[o].rs].L[0], t[t[o].rs].L[1], t[t[o].rs].R[0], t[t[o].rs].R[1]) : inf;
		if(a <= b) query1(t[o].ls, x), query1(t[o].rs, x);
		else query1(t[o].rs, x), query1(t[o].ls, x);
	}

	int h(int x, int y, int lx, int ly, int rx, int ry) {
		return max(abs(x-lx), abs(x-rx)) + max(abs(y-ly), abs(y-ry));
	}

	void query2(int o, int x) {
		if(!o) return;
		if(h(t[x].x[0], t[x].x[1], t[o].L[0], t[o].L[1], t[o].R[0], t[o].R[1]) < ansy) return;
		ansy = max(ansy, h(t[x].x[0], t[x].x[1], t[o].x[0], t[o].x[1], t[o].x[0], t[o].x[1]));
		int a = t[o].ls ? h(t[x].x[0], t[x].x[1], t[t[o].ls].L[0], t[t[o].ls].L[1], t[t[o].ls].R[0], t[t[o].ls].R[1]) : -inf;
		int b = t[o].rs ? h(t[x].x[0], t[x].x[1], t[t[o].rs].L[0], t[t[o].rs].L[1], t[t[o].rs].R[0], t[t[o].rs].R[1]) : -inf;
		if(a >= b) query2(t[o].ls, x), query2(t[o].rs, x);
		else query2(t[o].rs, x), query2(t[o].ls, x);
	}
} kdt;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &t[i].x[0], &t[i].x[1]);
		g[i] = i;
	}
	rt = kdt.build(1, n, 0);

	for(int i = 1; i <= n; i++) {
		ansx = inf, ansy = 0;
		kdt.query1(rt, i); kdt.query2(rt, i);
		ans = min(ans, ansy - ansx);
	}
	printf("%d\n", ans);
	return 0;
}

一直 10pts，不太清楚是什么原因