post.cpp

编程计算n个居民点到邮局的距离总和的最小值。 &#1048720

#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<stdlib.h>
ifstream in("input.txt");
ofstream out("output.txt");
int distance(int x1,int y1,int x2,int y2)
{
	return abs(x1-x2)+abs(y1-y2);
}
void swap(int&x,int&y)
{
	int z;
	z=x;x=y;y=z;
}
int partition(int a[20001],int p,int r)
{
	int i=p;
	int j=r+1;
	int x=a[p];
	while(true)
	{
		while(a[++i]<x);
		while(a[--j]>x);
		if(i>=j) break;
		swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

int RandomizedPatition(int a[20001],int p,int r)
{
	int i=p+rand()%(r-p+1);
	swap(a[i],a[p]);
	return partition(a,p,r);
}
int Randomizedquicksort(int a[20001],int p,int r)
{
	if(p<r)
	{
		int q=RandomizedPatition(a,p,r);
        Randomizedquicksort(a,p,q-1);
		Randomizedquicksort(a,q+1,r);
	}
	return *a;
}

int main()
{
	if(!in)
	{
		cout<<"the input.txt is not existed!"<<endl;
		
	}
	int a[20001],b[20001],n,i;long int sum;
	in>>n;
	for(i=0;i<n;i++)
	{in>>a[i]>>b[i];}

	*a= Randomizedquicksort(a,0,n-1);

	*b= Randomizedquicksort(b,0,n-1);
	int h=n/2;
	for(i=0;i<n;i++)
	{
		if(i==0)
			sum=distance(a[0],b[0],a[h],b[h]);
		else
			sum=sum+distance(a[i],b[i],a[h],b[h]);
	}
	out<<sum;
	return 0;
}