邮局选址问题

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

结果输出:

n 个居民点到邮局的距离总和的最小值。

例如
输入 输出

5 10

1 2

2 2

1 3

3 -2

3 3

解题思路：

因为街区中任意2 点(x 1,y 1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y 1-y2|度量所以我们可以将任意2点的距离可以看作为x坐标上的距离|x1-x2|和y坐标的距离|y 1-y2|之和。这样我们容易想到输油管道问题那个题目(我博客的第一篇文章)，所以我们可以将这个2维的题目拆分为2个一维然后将它们合并就行了。

一 找出x坐标(此时可忽略y坐标)的最优点 参考输油管道问题 可知最优点是中点，可以用 1.线性时间找中位数，2.先排序在找中位数 (因为输油管道问题是用的线性时间做的所以这个我贴的代码是用的排序)

二 找出y坐标(此时可忽略x坐标)的最优点 参考输油管道问题可知最优点是中点，可以用 1.线性时间找中位数，2.先排序在找中位数(因为输油管道问题是用的线性时间做的所以这个我贴的代码是用的排序)

三 合并 将x ,y坐标所求的距离和相加即是最有值。

#include<iostream>
#include<cmath>
using namespace std;
void Rs(int a[],int p,int r);
int pa(int a[],int p,int r);
int main()
{
int n;
int sum=0;
int x[1000];//x坐标
int y[1000];//y坐标
int dy;//y坐标中位数
int dx;//x坐标中位数
cin>>n;
for(int i=0;i<n;i++) cin>>x[i]>>y[i];
Rs(x,0,n-1);  
Rs(y,0,n-1);
dx=x[n/2];
dy=y[n/2];
for(i=0; i<n; i++) 
sum+=abs(x[i]-dx);//计算x坐标和
for(i=0; i<n; i++)
sum+=abs(y[i]-dy);//计算y坐标和
cout<<sum;
return 0;
}                                                                                                        
int pa(int a[],int p,int r)
{
int i=p,j=r+1;
int x=a[p];
	while(1)
	{
	while(a[++i]<x&&i<r);
	while(a[--j]>x);
	if(i>=j)	
	break;
	int tmp=a[i];	
	a[i]=a[j];
	a[j]=tmp;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void Rs(int a[],int p,int r)
{
if(p<r)
{
int q=pa(a,p,r);
Rs(a,p,q-1);
Rs(a,q+1,r);
}
}