An online retailer has robots that collect items from different locations in a warehouse to fulfill customer orders. Given a set of items and their locations, a robot starts from a packing station, collects all the items, and returns to the packing station quickly. How would you design an algorithm that finds the shortest route? The goal of the assignment is to find the shortest route for the robot. Desgin a brute-force algorithm that recursively enumerates all possible routes and determines the shortest route. For simplicity, we use non-negative integer x,y coordinates for the locations and assume a robot can travel from one location to another via a straight line (ie, no stationary or moving obstacles).

The program prints the shortest route (from a packing station and back to the packing station) to the standard output (screen). The location name, x, y, and distance from the previous location is on a line and the total distance is on the second last line. All distance values have 2 decimal places. The first and last locations are the packing station, and the first location has a distance value of 0.00 from the previous location. If more than one route has the smallest distance, output the route that is alphabetically earlier. For example, P, A, B, C, P would be earlier than P, C, B, A, P

Sample Input:

6

PackingStation 0 0

Airpods 0 3

Book 2 0

Coffee 2 3

Dress 2 6

Earphones 0 6

Sample Output:

PackingStation 0 0 0.00

Airpods 0 3 3.00

Earphones 0 6 3.00

Dress 2 6 2.00

Coffee 2 3 3.00

Book 2 0 3.00

PackingStation 0 0 2.00

16.00