Connecting Cities by Grid

Difficulty: 2400 6000 ms 128 MB

geometry greedy

N cities lie on a grid; the cost to link two cities is their Manhattan distance. Print the minimum spanning-tree cost.

Input: the first line has N; the next N lines have distinct points x y.

Output: the minimum total connection cost.

Constraints:

• 1 ≤ N ≤ 10³
• |coordinates| ≤ 10⁶

Sample Tests

3
0 0
0 5
3 3

10

1
2 2

0

Read the Editorial