Description

This problem is a simplified version of the famous NP-complete problem.

There are $n\ (n \le 1000)$ points on the Cartesian plane. Each point has coordinates $(x, y)$, where $-2^{31} < x, y < 2^{31}$ and both are integers. The cost to travel between any two points is the Euclidean distance between them. Your task is to compute the shortest bitonic tour.

Input Format

The first line contains an integer $n$.

Each of the next $n$ lines contains two integers $x, y$, representing the coordinates of a point.

It is guaranteed that there are no duplicate points, and that both the westernmost point and the easternmost point are unique.

Output Format

Output one line: the length of the shortest tour, with $2$ decimal places.

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

25.58

Hint

Source: Introduction to Algorithms (Second Edition), 15-1.

Translated by ChatGPT 5