P1523 Traveling Salesman, Simplified

The Euclidean Traveling Salesman problem, also known as the "货郎担" problem, has long challenged mathematicians and computer scientists around the world. No existing algorithm can compute an optimal solution in polynomial time on a deterministic machine, but there are algorithms that can compute a near-optimal solution in polynomial time. To simplify the problem while ensuring that an optimal solution can be found in polynomial time, J. L. Bentley proposed a Hamiltonian tour called the bitonic tour. Its requirements are: for any two points $(a, b)$, the travel cost is symmetric, i.e., $\mathrm{dist}(a, b) = \mathrm{dist}(b, a)$, and every pair of points is mutually reachable. The tour must go monotonically from the westernmost point to the easternmost point, then monotonically return to the westernmost point, forming a Hamiltonian cycle.

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.

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 one line: the length of the shortest tour, with $2$ decimal places.

Source: Introduction to Algorithms (Second Edition), 15-1. Translated by ChatGPT 5