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 far-side 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 x-coordinate. From there, the optimal path should visit locations at strictly increasing x-coordinates until Pete’s Parlour is reached at the rightmost x-coordinate. From here, the optimal return path should visit any and all unseen locations in strictly decreasing x-coordinates.

Note that the x-coordinate 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:
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: 2019-08-08 10:40:48

You can do better than O(n^3)

Simes: 2019-06-02 19:08:40

Don't trust spoj toolkit for any testcases with numbers above sqrt(2^31)
4
1 100
2 1
3 71000
4 5

pk845: 2018-07-14 20:04:54

given Time Limit is 1sec but my code gives AC with 3.1 sec. Why??
also by seeing the constraints (mainly time limit) I don't implement O(n^3) solution and wasted a lot of time :(
please correct the time limit.
thanku!

Last edit: 2018-07-14 20:18:26
Sigma Kappa: 2017-06-01 06:47:35

Reminiscent of the Bitonic TSP problem.

binarybleed: 2017-01-08 18:03:22

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

edit: AC. was some silly mistake.

Last edit: 2017-01-08 19:26:34
theph0enix: 2016-06-17 09:17:42

Slowest solution... 0.35s with bottom up O(n^2) space :(
@rohitsuri1410: Yes , input is already sorted with respect to x.
@dk_15: In that case it would be 30.00 not 30.

Last edit: 2016-07-07 10:26:31
dk_15: 2016-03-22 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: 2016-03-16 17:59:22

Is the input sorted with respect to X coordinates?


Added by:Darragh Griffin
Date:2016-02-23
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