Min Cost to Connect All Points

Medium

graphminimum-spanning-treeprim

You are given points on a 2D plane. The cost to connect two points is their Manhattan distance |x₁−x₂| + |y₁−y₂|. Return the minimum total cost to make all points connected (directly or indirectly) — i.e., the weight of a minimum spanning tree.

Input

Line 1: n 2 — the number of points and the coordinate count
Next n lines: x y for each point

Output: the minimum total cost.

Example 1

Input:

Output:

Edges (0,0)-(2,2), (2,2)-(5,2), (5,2)-(7,0), (2,2)-(3,10) cost 4+3+4+9.

Example 2

Input:

Output:

Constraints

1 ≤ n ≤ 1000
-10^6 ≤ coordinates ≤ 10^6
All points distinct.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Min Cost to Connect All Points

Medium

graphminimum-spanning-treeprim

Input

Line 1: n 2 — the number of points and the coordinate count
Next n lines: x y for each point

Output: the minimum total cost.

Example 1

Input:

Output:

Edges (0,0)-(2,2), (2,2)-(5,2), (5,2)-(7,0), (2,2)-(3,10) cost 4+3+4+9.

Example 2

Input:

Output:

Constraints

1 ≤ n ≤ 1000
-10^6 ≤ coordinates ≤ 10^6
All points distinct.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.