南郵OJ 1208郵便局の立地問題

郵便局の立地問題
時間制限(通常/Java) : 
1000 MS/ 3000 MS          実行メモリ制限:65536 KByte
コミット合計:203           テスト合格:112 
試合の説明
東西と南北に整然とした街に分かれている都市では、nの住民点が異なる街に散らばっている.x座標で東西を表し、y座標で南北を表す.各住民点の位置は座標(x,y)で表すことができる.ブロック内の任意の2点(x 1,y 1)と(x 2,y 2)との間の距離は、数値|x 1−x 2|+|y 1−y 2|で測定することができる.住民たちは都市の中で郵便局を設立する最適な位置を選んで、nの住民点から郵便局までの距離の総和を最小限に抑えることを望んでいる.n個の住民点の位置を与え,n個の住民点から郵便局までの距離の総和の最小値をプログラミングして計算した.
入力
入力ファイルの1行目は住民点数n,1<=n,=10000である.次にn行は住民点の位置であり、行ごとに2つの整数xとy,−1000,<=x,y<=10000である.
しゅつりょく
出力1行目の数はn個の住民点から郵便局までの距離の総和の最小値である.
サンプル入力
5 1 2 2 2 1 3 3 -2 3 3
サンプル出力
10
テーマソース
アルゴリズム設計と実験問題解

#include<stdio.h>
#include<stdlib.h>

int x[10010];
int y[10010];

int partition(int *a,int l,int r){
	int t=a[l],i=l,j=r;
	while(i<j){
		while(i<j && a[j]>=t){
			--j;
		}
		a[i] = a[j];
		while(i<j && a[i]<=t){
			++i;
		}
		a[j] = a[i];
	}
	a[i] = t;
	return i;
}

int randomized_partition(int *a,int l,int r){
	int i=rand()%(r-l+1)+l;
	int temp=a[l];
	a[l] = a[i];
	a[i] = temp;
	return partition(a,l,r);
}
int select(int a[],int l,int r,int k){
	if(l>=r){
		return a[l];
	}
	int m=randomized_partition(a,l,r);
	int j=m-l;			//☆
	if(j==k){
		return a[m];
	}else if(j<k){
		return select(a,m+1,r,k-j-1);	//a[m]      m ，  a[0]~a[r]     k  a[m+1]~a[r] (k-j-1) 
	}else{								//      j   k
		return select(a,l,m-1,k);		//0 1 2 3 4 5 6
	}									//        0 1-------> (k-j-1)      0   
}

int main(){
	int n,i,x1,y1;
	long sum=0;
	scanf("%d",&n);
	for(i=0;i<n;++i){
		scanf("%d%d",&x[i],&y[i]);
	}
	x1 = select(x,0,n-1,n/2);
	y1 = select(y,0,n-1,n/2);
	for(i=0;i<n;++i){
		if(x[i]>x1){
			sum += x[i]-x1;
		}else{
			sum += x1-x[i];
		}
		if(y[i]>y1){
			sum += y[i]-y1;
		}else{
			sum += y1-y[i];
		}
	}
	printf("%d
",sum);
}