Travelling Salesman Problem

You are given multiple instances of the Travelling Salesman Problem (TSP). In each instance, you are provided with n cities and their coordinates. Your task is to compute the length of the shortest possible route that visits each city exactly once and returns to the starting city.

The distance between two cities with coordinates \((x_1, y_1)\) and \((x_2, y_2)\) is given by the Euclidean distance formula: \(\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\).

Note: Since the number of cities is small, a brute-force method through all permutations will work within the allowed time constraints.

inputFormat

The input consists of multiple test cases. Each test case begins with a positive integer n (the number of cities). This is followed by n lines, each containing two integers representing the x and y coordinates of a city. The end of input is indicated by a line with a single 0, which should not be processed.

outputFormat

For each test case, output a single line containing the length of the shortest route. The result must be formatted to six decimal places.## sample

4
0 0
0 1
1 0
1 1
0

4.000000