街區最短路徑問題 7 （數學 曼哈頓距離）

街區最短路徑問題

時間限制： 3000 ms | 記憶體限制： 65535 KB 難度： 4

描述

一個街區有很多住戶，街區的街道隻能為東西、南北兩種方向。

住戶隻可以沿着街道行走。

各個街道之間的間隔相等。

用(x,y)來表示住戶坐在的街區。

例如（4,20），表示使用者在東西方向第4個街道，南北方向第20個街道。

現在要建一個郵局，使得各個住戶到郵局的距離之和最少。

求現在這個郵局應該建在那個地方使得所有住戶距離之和最小；

輸入

第一行一個整數n<20，表示有n組測試資料，下面是n組資料;

每組第一行一個整數m<20,表示本組有m個住戶，下面的m行每行有兩個整數0<x,y<100，表示某個使用者所在街區的坐标。

m行後是新一組的資料；

輸出

每組資料輸出到郵局最小的距離和，回車結束；

樣例輸入

2
3
1 1
2 1
1 2
5
2 9 
5 20
11 9
1 1
1 20
      

樣例輸出

2
44
      

/*
曼哈頓距離：兩點在南北方向上的距離加上在東西方向上的距離，即d（i，j）=|xi-xj|+|yi-yj|。
對于一個具有正南正北、正東正西方向規則布局的城鎮街道，從一點到達另一點的距離正是在南北
方向上旅行的距離加上在東西方向上旅行的距離。

思路：因為隻能東西和南北方向走，是以先把南北（X）和東西（Y）方向的坐标分開，分别求它們的最值，
然後相加即可。
           
   

經分析可知，此點的坐标一定是x軸的中點和y軸的中點處，這樣才能保證到所有的居民處距離最小。
           
   

*/
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
	int t,n,i,j,sum;
	int x[110],y[110];
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d%d",&x[i],&y[i]);
		sort(x,x+n);
		sort(y,y+n);
		for(i=0;i<n/2;i++)
		{
			sum+=(x[n-i-1]-x[i]+y[n-i-1]-y[i]);
		}
		printf("%d\n",sum);
	}
	return 0;
}