输油管道.cpp

输油管道

#include<iostream>
#include<fstream>
using namespace std;

template<class T>
inline void Swap(T &a,T &b){
	T temp=a;
	a=b;
	b=temp;
}

template<class T>
void BubbleSort(T a[],int p,int r){
	for(int i=r;i>p;i--)
		for(int j=p;j<i;j++)
			if(a[j]>a[j+1])
				Swap(a[j],a[j+1]);
}

template<class T>
int Partition(T a[],int p,int r,int pos){
	Swap(a[pos],a[p]);
	int i=p,j=r+1;
	T x=a[p];
	while(true){
		while(++i<j&&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;
}

template<class T>
T Select(T a[],int p,int r,int k,int &pos){
	if(r-p+1<75){
		BubbleSort(a,p,r);
		pos=p+k-1;
		return a[p+k-1];
	}
	int r1=r-p;
	for(int i=0;i<=r1/5;i++){
		if(p+i*5+4<=r){
			BubbleSort(a,p+i*5,p+i*5+4);
			Swap(a[p+5*i+2],a[p+i]);
		}
		else{
			BubbleSort(a,p+i*5,r);
			Swap(a[p+(r1-i*5+1)/2+(i-1)*5],a[p+i]);
		}
	}
	int pp;
	T x=Select(a,p,p+r1/5,(r1/5+1)/2+1,pp);
	i=Partition(a,p,r,pp);
	int j=i-p+1;
	if(k==j){
		pos=i;
		return a[i];
	}
	else 
		if(k<=j)
			return Select(a,p,i,k,pp);
		else
			return Select(a,i+1,r,k-j,pp);
}

template<class T>
T Sum_distance(T a[],int n,const T &x){
	T sum=0;
	for(int i=0;i<n;i++)
		sum+=abs(a[i]-x);
	return sum;
}

void main(){
	int n;
	ifstream infile("input.txt");
	ofstream outfile("output.txt");
	infile>>n;
	int *x=new int[n],*y=new int[n];
	for(int i=0;i<n;i++)
		infile>>x[i]>>y[i];
	int pos;
	int mid=Select(y,0,n-1,n/2+1,pos);
	int sum=Sum_distance(y,n,mid);
	outfile<<sum<<endl;
}