SWUST.OJ 493: PostOffice

493: PostOffice
题目描述
　　在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。 　　街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。 　　居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 　　任务：给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
输入
　　第1 行是居民点数n，1 < = n < =10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000 < =x，y < =10000。
输出
n 个居民点到邮局的距离总和的最小值。
样例输入
5
1 2
2 2
1 3
3 -2
3 3
样例输出
10

#include<iostream>
#include<algorithm>
using namespace std;
//void 
 int main()
 {
 	int sum,x1,y1;
 	int num;
 	cin>>num;
 	int x[num]={0},y[num]={0};
 	for(int j=0;j<num;j++)
 	{
 		cin>>x[j]>>y[j];
	 }
 	sort(x,x+num);
 	sort(y,y+num);
 	x1=x[num/2];
 	y1=y[num/2];
 	for(int i=0;i<num;i++)
 	{
 		sum+=abs(x1-x[i]);
 		sum+=abs(y1-y[i]);
	 }
	cout<<sum<<endl;
	return 0;
 }

对于多个居民点，设想所有点的x在一条直线上（平移），最中间点的 x 即是邮局的 x 坐标；邮局的 y 坐标同理。