8583: DPL_2_C : Bitonic Traveling Salesman Problem (Bitonic TSP)
[Creator : ]
Description
For given $N$ points in the 2D Euclidean plane, find the distance of the shortest tour that meets the following criteria:
-
Visit the points according to the following steps:
- It starts from the leftmost point (starting point), goes strictly from left to right, and then visits the rightmost point (turn-around point).
- Then it starts from the turn-around point, goes strictly from right to left, and then back to the starting point.
- Through the processes 1. 2., the tour must visit each point at least once.
Input
The input data is given in the following format:
$N$
$x_1\ y_1$
$x_2\ y_2$
$...$
$x_N\ y_N$
$N$
$x_1\ y_1$
$x_2\ y_2$
$...$
$x_N\ y_N$
Output
Print the distance of the shortest tour in a line. The output should not have an error greater than 0.0001.
Constraints
$2≤N≤1000$
$−1000≤x_i,y_i≤1000$
$x_i$ differ from each other
The given points are already sorted by x-coordinates
$−1000≤x_i,y_i≤1000$
$x_i$ differ from each other
The given points are already sorted by x-coordinates
Sample 1 Input
3
0 0
1 1
2 0
Sample 1 Output
4.82842712
Sample 2 Input
4
0 1
1 2
2 0
3 1
Sample 2 Output
7.30056308
Sample 3 Input
5
0 0
1 2
2 1
3 2
4 0
Sample 3 Output
10.94427191
HINT
相同题目：DPL_2_C。