Minimum Cost to Connect All Points

Moderate

0/80

Average time to solve is 30m

Contributed by

2 upvotes

+2 more companies

Problem statement

You are given an array, ‘COORDINATES’ that represents the integer coordinates of some points on a 2D plane. Your task is to find the minimum cost to make all the points connected where the cost of connecting two points: (x1, y1) and (x2, y2) is equal to the manhattan distance between them, i.e., |x1 - x2| + |y1 - y2|.

Note:

1) An element of the ‘COORDINATES’ array is a pair of ‘X' and ‘Y’ coordinates of a point, i.e., COORDINATES[i] =  (Xi, Yi).

2) |DISTANCE| represents the absolute value of distance.

3) All points are considered to be connected if there is exactly one simple path between two points.

4) According to Wikipedia, a simple path is a path in a plane that does not have repeating points.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of points in the ‘COORDINATES’ array.

The next ‘N’ lines of each test case contain two space-separated integers representing the ‘X and ‘Y’ coordinates of a point.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum cost to make all the points connected.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 1000
10 ^ -6 <= X, Y <= 10 ^ 6
All points are distinct.

Where ‘T’ is the number of test cases, ‘N’ is the number of points in the ‘COORDINATES’ array, ‘X’, ‘Y’ is the x and y coordinates of a point, respectively.

Time limit: 1 sec.

Sample Input 1:

Sample Output 1:

23
44

Explanation of Sample Output 1:

Test Case 1 :  
Connecting (1, 4) and (2, 6) will cost 3.
Connecting (2, 6) and (5, 3) will cost 5.
Connecting (5, 3) and (8, 2) will cost 4.
Connecting (8, 2) and (7, 3) will cost 11.
Total cost = 3 + 5 + 4 + 11 = 23, which is minimum.

Test Case 2 : 
Connecting (1, -4) and (-5, -3) will cost 7.
Connecting (-5, -3) and (8, 6) will cost 17.
Connecting (8, 6) and (0, 18) will cost 20.
Total cost = 7 + 17 + 20 = 44, which is minimum.

Sample Input 2:

Sample Output 2:

0
153282

Console