1038. Minimum Cost to Connect All Points

Given points on a 2D plane, connecting two points costs their Manhattan distance |x1-x2| + |y1-y2|. Return the minimum total cost to connect all points so that any point is reachable from any other (a minimum spanning tree over the complete graph). The input is JSON {points}.

Input: JSON {points}.

Output: Integer — the minimum connection cost.

Examples

Input: {"points":[[0,0],[2,2],[3,10],[5,2],[7,0]]}
Output: 20
Explanation: Minimum spanning tree of Manhattan distances.

Input: {"points":[[0,0]]}
Output: 0
Explanation: Single point.

Input: {"points":[[3,12],[-2,5],[-4,1]]}
Output: 18
Explanation: Two connecting edges.

Constraints

• 1<=points<=1000

Asked by