題意：
給你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 方向就可以求出此題的解了。
代碼：
[cpp]
<span style="font-family:FangSong_GB2312;font-size:18px;">#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));
}
}
</span>
