#234MediumGraphs· Minimum Spanning Tree with Prim

Cheapest Sensor Mesh

A farm places soil sensors at known coordinates and wants every sensor to be able to relay data to every other one through a wired mesh. A cable can be laid directly between any two sensors, and its cost equals the **Manhattan distance** between them: `|x1 - x2| + |y1 - y2|`. The cables form a network, so the sensors must end up connected, directly or through other sensors. Return the minimum total cable cost that connects all sensors. A single sensor needs no cable.

Input format

`points`: an array of `[x, y]` sensor coordinates.

Output format

An integer: the minimum total cost.

Examples

Input: points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]

Output: 20

One cheapest mesh uses the cables (0,0)-(2,2) cost 4, (2,2)-(5,2) cost 3, (5,2)-(7,0) cost 4 and (2,2)-(3,10) cost 9, for a total of 20.

Input: points = [[0, 0]]

Output: 0

One sensor is already connected to itself, so the cost is 0.

Input: points = [[0, 0], [1, 1], [1, 0], [-1, 1]]

Output: 4

Cables (0,0)-(1,0) and (1,0)-(1,1) cost 1 each; the last sensor (-1,1) is closest to (0,0) or (1,1) at cost 2, so the total is 4.

Constraints

1 <= points.length <= 1000
-10^5 <= x, y <= 10^5
All points are distinct.

#graphs
#minimum-spanning-tree
#prim
#greedy
#geometry