//输油管道问题
 
这个题，虽然说给出了井的x,y坐标，但是要修建的主管道却只是一条横向的，而且其余管道也只是到这条管道的竖向距离。
那么，就转换为确定一条直线 y = m，使得其它个点到这条直线的距离最多。也许不需要多的提示，大家的直觉就会想到应该
选所有y值的中点。但是，这个的证明却不是那么的明显。
 
证明如下：
   设所有的y值系列为y1,y2,...,yn，并且假设这个是按递增排列的。我们要求的是Sum = Σ|yi-m|(1<=i<=n),
   
   1）显然假如选小于y1或者大于yn的y=m都不会比选y1或者yn更好。
   2）如果选y1或者yn，那么|y1-m|+|yn-m| = |yn-y1|都是一样的结果，甚至选y1和yn之间的任意一个值。
   3）如此继续下去，对于y2和yn，也有2）所描述的性质
   4）继续到最后，只需要取最中间一对点之间的值即可，如果n是奇数，那么就是中间的点，如果n是偶数，取任意一个中间
        点都可以。
 
   通过上面证明，我们可以选取第y(n/2 + 1)作为修建主管道的地方。当然这可能是唯一的最优选择，或者无数个最优选择中的一个。
那么现在已经转换为求中位数了，求中位数的办法最简单的是对序列排序然后取中间的即可。算法导论上有一种平均代价O(n)的办法，
思路类似于快速排序，快排的每一次操作都是划分数组，前小后大，如果我们也这一次次去划分数组，刚好轴元素处于我们要求的那个位置
上那么就达到我们的目的了，下面的代码中Select函数就是求一个数组的中位数。
 
 
package wkx;
 
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
 
public class Test {
 
	private static int randomPartition(int[] data, int beg, int end) {
		Random rand = new Random(new Date().getTime());
		int pos = rand.nextInt(end - beg + 1) + beg;
		System.out.println("pos=" + pos);
		int t = data[beg];
		data[beg] = data[pos];
		data[pos] = t;
 
		int key = data[beg];
		while (beg < end) {
			while (beg < end && data[end] >= key)
				end--;
			data[beg] = data[end];
			while (beg < end && data[beg] <= key)
				beg++;
			data[end] = data[beg];
		}
		data[beg] = key;
		return beg;
	}
 
	private static int select(int[] data, int beg, int end, int k) {
		if (beg == end)
			return data[beg];
		int mid = randomPartition(data, beg, end);
		int size = mid - beg + 1;
		if (k <= size)
			return select(data, beg, mid, k);
		else
			return select(data, mid + 1, end, k - size);
	}
 
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			List<Integer> l=new ArrayList<Integer>();
			int len = in.nextInt();
			for(int i=0;i<len;i++){
				in.nextInt();
				l.add(in.nextInt());
			}
			Collections.sort(l);
			int[] data=new int[len];
			int t=0;
			for(Iterator<Integer>it=l.iterator();it.hasNext();)
				data[t++]=it.next().intValue();
			int m=select(data,0,len-1,len/2);
			int sum=0;
			for(int i=0;i<len;i++){
				sum+=Math.abs(m-data[i]);
			}
			System.out.println(sum);
		}
	}
 
}