Point

There are a lot of points on a plane. We need to find the closest point for each point. To be special, “closest” refers to unusual distance: the distance of two points A, B is defined by this:
Distance (A, B) = max (|Ax – Bx|, |Ay – By|)
Please output the sum of the distances.

The input consists of multiply test cases. The first line of each test case contain one integer, n (2 <= n <= 100000), which is the number of points. Each of the next n lines contains two integer, x, y (0 <= x, y <= 1000000000), indicating the coordinate of a point. Two points might have the same coordinate.

Output the sum of the distances.

3
0 0
1 1
3 3

4

momodi

HDOJ Monthly Contest – 2010.04.04