The town of Even-ville is getting into the car infotainment business. There is a request to implement some features of a GPS navigation system with a built in recommendation system. As a reminder a GPS uses graph and geometric algorithms to calculate distances and map a route. One of the geometric problems is the closest-pair problem. Given a set of points, the closest-pair problem is to find the two points that are nearest to each other. We are asked to use the second closest pair solution for our recommendation system.
We will first write a program that computes the distances between all pair of points and find the one with the second smallest distance as follows:
1. Ask the user to enter the number of points.
2. Ask the user to enter x and y positions for each point. S tore the positions in a 2-D array. What should the dimensions of the 2-D array be?
3. Compute the distance between the first two points and initialize the variable that represents the second shortest distance. Recall that the distance between the two points (x1, y1) and (x2, y2) is computed by taking the square root of the quantity (x1 - x2)^2 + (y1 - y2)^2.
4. Use a nested for loop to compute the distance for every two points and update the second shortest distance and the two points with the second shortest distance.
5. Display the second shortest distance and the second closest two points.