2 u012698889 u012698889 于 2013.11.03 09:41 提问

这里有一题ACM的小题目,求众神解答。帮写个程序。小弟冰天雪地裸奔哭嚎以示感谢!

邮局选址:
在一个按照东西和南北方向划分成规整街区的城市里,n 个居民点散乱的分布在不同的街区中。用X坐标表示东西向,用Y坐标表示南北向,各居民点的位置可以有坐标(XY)表示。街区中任意2点(X1,Y1)和(X2,Y2)质检的距离可以用数值丨X1-X2丨+丨Y1-Y2丨度量。居民们希望在城市中选择建立邮局的最佳位置,使n 个居民点到邮局的距离总和最小。
编程任务:
给定n 个居民点的位置,计算n个居民点到邮局的距离总和的最小值
数据输入:
由文件input.txt提供输入数据,文件的第1行是居民点数n,1<=n<=10000,接下来n行是居民点的位置,每行2个整数X和Y ,-10000<=x,y<=10000。
结果输出:
程序运行结束时,按计算结果输出文件output.txt中。文件的第一行中的数是n个居民点到邮局的距离总和的最小值。
输入文件实例
input.txt
5
1 2
2 2
1 3
3 -2
3 3
输出文件实例
output.txt
10

1个回答

u012698889
u012698889   2013.11.03 10:08
已采纳

#include
using namespace std;
void QuickSort(int arry[],int l,int h);
int main()
{ int i,j,n,l,h,x,y,a,b;
int sum1=0,sum2=0;
cin >> n;
l=0;
h=n-1;
int arry[10000][2];
int *x1=new int[n];
int *y1=new int[n];
for(i=0;i<n;i++)
for(j=0;j<2;j++)
{scanf("%d",&arry[i][j]);}
for(i=0;i<n;i++)
{ x1[i]=arry[i][0];
y1[i]=arry[i][1];}
QuickSort( x1,l, h);
QuickSort( y1,l, h);
x=x1[(n -1)/2];
y=y1[(n -1)/2];
for(i=0;i<n;i++)
{ a=arry[i][0]-x;
if((arry[i][0]-x)<0)
{a=x-arry[i][0];}
b=arry[i][1]-y;
if((arry[i][1]-y)<0)
{b=y-arry[i][1];}
sum1+=a;
sum2+=b;}
cout<<sum1+sum2<<endl;
return 0;}
void QuickSort(int arry[],int l,int h)
{ int i=l, j=h; //低LOW ,高HIGH
int temp = arry[l]; //取第一个做标准数据元书的
while(i<j)
{ while(i<j && temp <=arry[j])j--;//右端扫描
if(i<j)
{arry[i]=arry[j];
i++;}
while(i<j && arry[i] < temp)i++;
if(i<j)
{arry[j]=arry[i];
j--;}}
arry[i]=temp;
if(l<i)QuickSort( arry, l,i-1);
if(i<h)QuickSort( arry, j+1,h);}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!