Connecting Cities by Grid
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 ≤ 103
- |coordinates| ≤ 106
Sample Tests
Input 1
3 0 0 0 5 3 3
Output 1
10
Input 2
1 2 2
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.