题意：
给你n个点。选择一个点，是其他点到这个点的Manhattan 距离最小
思路：
平面上两点间的 Manhattan 距离为 |x1-x2| + |y1-y2|所以X 方向的距离与 Y 方向上的距离可以分开来处理。假设我们以 (xi,yi) 作为开会的地点，那么其余的点到该开会地点所需的时间为 X 方向上到 xi 所需要的时间加上 Y 方向上到 yi 所需要的时间。所以可以分别对x方向，y方向各点作文开会地点时，其他点到这个点的距离。
单独处理一维的时候，相当于求其他点到当前点的距离之和，如果点事已序的，可以O（n）求出。
所以我们对当前方向可以先排序，然后求其他点到某一个点的距离时，可以得到一个递推公式，f[i] = f[i-1] + (2 * i – n) * (x[i] – x[i - 1]);依次处理 X 方向 Y 方向就可以求出此题的解了。代码：
#include<cstdio> #include<cmath> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int N = 100002; struct node { long long a; int id; bool operator < (const node &a) const { return id < a.id; } }; node x[N], y[N]; node X[N], Y[N]; bool cmp(node a, node b) { return a.a < b.a; } void ready(int n) { sort(x, x + n, cmp); sort(y, y + n, cmp); memset(X, 0, sizeof(X)); memset(Y, 0, sizeof(Y)); for(int i = 1; i < n; i ++) { X[0].a += x[i].a - x[0].a; Y[0].a += y[i].a - y[0].a; } X[0].id = x[0].id; Y[0].id = y[0].id; for(int i = 1; i < n; i ++) { X[i].a = X[i - 1].a + (2 * i - n) * (x[i].a - x[i - 1].a); Y[i].a = Y[i - 1].a + (2 * i - n) * (y[i].a - y[i - 1].a); X[i].id = x[i].id; Y[i].id = y[i].id; } } long long solve(int n) { sort(X, X + n); sort(Y, Y + n); long long minn = X[0].a + Y[0].a; for( int i = 1; i < n; i ++) { if(X[i].a + Y[i].a < minn) minn = X[i].a + Y[i].a; } return minn; } int main() { int T, n; scanf("%d", &T); while(T--) { scanf("%d",&n); for(int i = 0; i < n; i ++) { scanf("%I64d%I64d", &x[i].a, &y[i].a); x[i].id = y[i].id = i; } ready(n); printf("%I64d\n", solve(n)); } }