hdu 4311

题意：
给你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>

补充：软件开发 , C++ ,