Time Limit: 40000/20000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
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.
HDOJ Monthly Contest – 2010.04.04