← 返回 bytedance 的题目列表Min Cost to Connect All Points
类型:online_judge
Problem: Min Cost to Connect All Points
You are given n points on a 2D plane, where points[i] = [xi, yi].
The cost to connect two points [xi, yi] and [xj, yj] is their Manhattan distance:
|xi - xj| + |yi - yj|
Return the minimum total cost to connect all points.
Requirements:
There can be at most one edge between any two points.
All points must be connected, meaning there is a path between every pair of points.
Return the minimum possible total cost.
Input Format
n
x1 y1
x2 y2
...
xn yn
Output Format
minimum total cost
Constraints
1 <= n <= 1000
-10^6 <= xi, yi <= 10^6
All points are distinct.
Example
Input:
5
0 0
2 2
3 10
5 2
7 0
Output:
20
Example
Input
5
0 0
2 2
3 10
5 2
7 0
Output
20