Traveling Salesman Problem: Minimum Travel Distance

You are given a set of n points in the Euclidean plane. Your task is to find the shortest possible route that visits each point exactly once and returns to the starting point. In other words, you need to solve a small instance of the Traveling Salesman Problem (TSP).

The distance between any two points \(p=(x_1,y_1)\) and \(q=(x_2,y_2)\) is defined as:

[ d(p,q) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} ]

The answer should be printed as the minimum travel distance rounded to two decimal places.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of points. Each of the following (n) lines contains two space-separated integers (x) and (y), representing the coordinates of a point.

outputFormat

Output the minimum travel distance (the total length of the optimal route) rounded to two decimal places to standard output (stdout).## sample

4
0 0
1 1
1 0
0 1

4.00