hdu4311 曼哈頓距離

http://acm.hdu.edu.cn/showproblem.php?pid=4311

Problem Description It has been ten years since TJU-ACM established. And in this year all the retired TJU-ACMers want to get together to celebrate the tenth anniversary. Because the retired TJU-ACMers may live in different places around the world, it may be hard to find out where to celebrate this meeting in order to minimize the sum travel time of all the retired TJU-ACMers.
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, only 4 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.

Input The first line is an integer T represents there are T test cases. (0 For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0
Output For each test case, output the minimal sum of travel times.
Sample Input

4
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2

Sample Output

26
20
20
56
Hint
In the first case, the meeting point is (-1,-2); the second is (0,0), the third is (3,1) and the last is (-2,2)

/**
hdu 4311 曼哈頓距離 
題目大意：在給定的n個點中選擇一個點，使得其他點到這個點的曼哈頓距離之和最小，求出這個最小的距離
解題思路：如果我們確定了這個點的坐標為 (x,y).xx為所有點的橫坐標之和,numlx表示該點左邊的點的個數，
          那麼lengx=(x*numlx-sumx[1~numlx-1])+(sumx[numlx~n]-x*(n-numlx))=x*(2*numlx-n)+xx-2*sum[1~numlx];
          對於縱坐標的處理類似。
          這些工作做好之後我們把n個點都枚舉1遍取最小就可以了。
*/
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn=100005;
struct note
{
    int x,y,id;
} a[maxn];
int x[maxn],y[maxn],n;
LL numx[maxn],numy[maxn];

bool cmp1(note a,note b)
{
    return a.x