AMBLE  Alicias Afternoon Amble
Alicia is staying in a hotel on the edge of town. She sets out in the morning with a list of landmarks to visit all across the city. This day of sightseeing will take her through the city, visiting a number of locations, all the way to the farside of city where she will pause for lunch at the prestigious Pete’s Polygon Pizza Parlour. Anything she misses must be visited on the return trip to the hotel in the evening.
Given the set of locations that Alicia would like to visit, find the length of the shortest tour which starts at her hotel, visits each of the locations, and returns back to the hotel. Beside the starting location, each location should be visited exactly once.
The starting hotel will be located at the leftmost xcoordinate. From there, the optimal path should visit locations at strictly increasing xcoordinates until Pete’s Parlour is reached at the rightmost xcoordinate. From here, the optimal return path should visit any and all unseen locations in strictly decreasing xcoordinates.
Note that the xcoordinate of each location will be unique.
Input
The first line of input contains a single integer N, 1 ≤ N ≤ 1000, representing the number of locations.
Each of the next n lines contains two integers X and Y, 0 ≤ X, Y ≤ 100000, representing the coordinates of the N locations.
The (X, Y) coordinates of all locations are given as integers on a Euclidean plane.
Output
The output should consist of a single decimal containing the the total length of the tour rounded to two decimal places. This should immediately be followed by a newline.
Example One
Input: 5
1 3
2 1
3 4
4 4
5 2
Output: 10.87
Example Two
Input: 10
4 1
13 4
21 3
25 9
28 10
42 1
43 2
50 4
67 10
68 9
Output: 131.65
hide comments
hodobox:
20190808 10:40:48
You can do better than O(n^3) 

Simes:
20190602 19:08:40
Don't trust spoj toolkit for any testcases with numbers above sqrt(2^31)


pk845:
20180714 20:04:54
given Time Limit is 1sec but my code gives AC with 3.1 sec. Why??


Sigma Kappa:
20170601 06:47:35
Reminiscent of the Bitonic TSP problem. 

binarybleed:
20170108 18:03:22
getting TLE. bottom up approach. Time Complexity: O(n^3). Space: O(n^2). Any hint?


theph0enix:
20160617 09:17:42
Slowest solution... 0.35s with bottom up O(n^2) space :(


dk_15:
20160322 20:31:26
should the output always have 2 digits after decimal... i mean in the case of ans is 30 den d output should be 30 or 30.00


rohitsuri1410:
20160316 17:59:22
Is the input sorted with respect to X coordinates?

Added by:  Darragh Griffin 
Date:  20160223 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: GOSU 
Resource:  Irish Collegiate Programming Contest 2015 http://acm.ucc.ie/irlcpc 