传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4039
【题解】
曼哈顿距离没法把坐标分开来计算，使得$x$部分最小，不一定就能使得$y$部分最小。
只能先转成切比雪夫距离（是可以实现上面的功能的），那么每个点的可行区域就是一个边平行于坐标轴的正方形。
求一下正方形的交，那么答案肯定在交中，交为空则impossible。
既然坐标独立，那么可以三分$x$坐标，再三分$y$坐标，这两个肯定是单峰函数。
由于一些奇怪的原因这题卡常，暴力写是$O(nlog^2n)$（三分常数有点大），过不去。
考虑优化，再把切比雪夫距离转成曼哈顿距离，这样就能快速计算曼哈顿距离和了。
只要分成x和y坐标考虑，然后每次询问，二分第一个大于x的，稍微统计下就行了。
最后我们三分的答案不一定是整数，在附近找一些点判下就行了。
复杂度$O(nlogn+log^3n)$
# include <stdio.h> # include <assert.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e5 + 10; const int mod = 1e9+7; const ll inf = 1e16; int n, d; ll xl, xr, yl, yr, x[M], y[M]; struct pa { ll x, y; pa() {} pa(ll x, ll y) : x(x), y(y) {} }p[M]; # define abs(x) ((x) >= 0 ? (x) : -(x)) struct Manhattan { ll p[M], s[M]; inline void set() { memset(s, 0, sizeof s); for (int i=1; i<=n; ++i) s[i] = s[i-1] + p[i]; } inline ll gs(int x, int y) { if(x>y) return 0; return s[y] - s[x-1]; } inline ll query(ll x) { if(x >= p[n]) return (ll)n*x-s[n]; int l = 1, r = n, mid, pos; while(1) { if(r-l <= 3) { for (int i=l; i<=r; ++i) { if(p[i] > x) { pos = i; break; } } break; } mid = l+r>>1; if(p[mid] > x) r = mid; else l = mid; } ll ret = (ll)(pos-1) * x - gs(1, pos-1) + gs(pos, n) - (ll)(n-pos+1) * x; return ret; } }X, Y; inline ll calc(ll x, ll y) { // ll ret = 0; // for (int i=1; i<=n; ++i) // ret += max(abs(x - p[i].x), abs(y - p[i].y)); // return ret*2; return X.query(x+y) + Y.query(x-y); } inline ll g(ll x) { ll l = yl, r = yr, mid1, mid2, t = inf, tmp, ans; while(1) { if(r-l <= 3) { for (ll i=l; i<=r; ++i) if((tmp = calc(x, i)) < t) t = tmp, ans = i; return ans; } mid1 = l+(r-l)/3.0, mid2 = r-(r-l)/3.0; if(calc(x, mid1) < calc(x, mid2)) r = mid2; else l = mid1; } assert(0); } inline void sol() { xl = yl = -inf, xr = yr = inf; for (int i=1; i<=n; ++i) { scanf("%lld%lld", &x[i], &y[i]); p[i] = pa(x[i] + y[i], x[i] - y[i]); } sort(x+1, x+n+1); sort(y+1, y+n+1); for (int i=1; i<=n; ++i) X.p[i] = (ll)x[i] * 2, Y.p[i] = (ll)y[i] * 2; X.set(), Y.set(); cin >> d; for (int i=1; i<=n; ++i) { xl = max(xl, p[i].x-d); yl = max(yl, p[i].y-d); xr = min(xr, p[i].x+d); yr = min(yr, p[i].y+d); } if(xl > xr || yl > yr) { puts("impossible"); return ; } ll l = xl, r = xr, mid1, mid2, r1, r2, t = inf, tmp, ans; while(1) { if(r-l <= 3) { for (ll i=l; i<=r; ++i) if((tmp = calc(i, g(i))) < t) t = tmp, ans = i; break; } mid1 = l+(r-l)/3.0, mid2 = r-(r-l)/3.0; r1 = g(mid1), r2 = g(mid2); if(calc(mid1, r1) < calc(mid2, r2)) r = mid2; else l = mid1; } l = ans; r = g(l); ans = inf; for (ll i=l-2, t; i<=l+2; ++i) for (ll j=r-2; j<=r+2; ++j) { if(i < xl || i > xr || j < yl || j > yr) continue; if((i+j)&1) continue; if((t = calc(i, j)) < ans) ans = t; } cout << ans/2 << endl; } int main() { while(cin >> n && n) sol(); return 0; }