This is a very simple problem. You are given $N$ points. Some points may be repeated. The weight (distance) between two points is given by the Manhattan distance between the two points. Find the weight of a Minimum Spanning Tree that spans these $N$ points.
The input consists of:
One line with one integer $N$ ($1 \leq N \leq 100\, 000$), the number of points,
$N$ lines each with two integers $x$ and $y$ ($0 \leq x,y < 1\, 000$), the coordinates of each point.
Output one line with a single integer: The weight of a Minimum Spanning Tree that spans these $N$ points.
Sample Input 1 | Sample Output 1 |
---|---|
4 0 0 0 1 1 0 1 1 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
5 0 0 10 0 10 0 11 1 12 2 |
14 |