SOLDIERS

来源POJ第1723题SOLDIERS

Description

N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

The soldiers want to get into a horizontal line next to each other (so that their final positions are (x,y), (x+1,y), …, (x+N-1,y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary.

The goal is to minimise the total number of moves of all the soldiers that takes them into such configuration.

Two or more soldiers must never occupy the same position at the same time.

Input

The first line of the input contains the integer N, 1 <= N <= 10000, the number of soldiers.
The following N lines of the input contain initial positions of the soldiers : for each i, 1 <= i <= N, the (i+1)st line of the input file contains a pair of integers x[i] and y[i] separated by a single blank character, representing the coordinates of the ith soldier, -10000 <= x[i],y[i] <= 10000.

Output

The first and the only line of the output should contain the minimum total number of moves that takes the soldiers into a horizontal line next to each other.

Sample Input

5
1 2
2 2
1 3
3 -2
3 3

Sample Output

8

其实本题求的是距离，反映到数学上，就是求两点之间的绝对值吗。

对于一个数列，其各点到此数列的中位数处的距离之和是最短的。

因此，分别对两个数列进行排序对于纵坐标，直接求出各点到中位数处的距离即可。对于横坐标，首先先将其排序后减去自身的位置，即x[i] - i,这是因为最终要求是在同一横排上，因而当x[i] - i，一样的时候，说明他们本身就是相邻的，最后通过构建出的x[i]-i数组，取中位数d[mid]-d[i]求和即可。

import java.util.*;

public class Main {
		public static void main(String[] args) {
			Scanner in = new Scanner(System.in);
			int len = in.nextInt();
			int [] dx = new int[len];
			int [] dy = new int[len];
			for(int i = 0 ; i < len ; i++){
				dx[i] = in.nextInt();
				dy[i] = in.nextInt();
			}
			Arrays.sort(dx);
			Arrays.sort(dy);
			for(int i = 1 ; i <= len ; i++)
				dx[i - 1] -= i;
			Arrays.sort(dx);
			int midx = dx[(len) / 2 ];
			int midy = dy[(len) / 2];
			int ans = 0;
			for(int i = 0 ; i < len ; i++){
				ans += Math.abs(midx - dx[i]) + Math.abs(midy - dy[i]);
			}
			System.out.println(ans);
		}
}