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: 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:
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)
|
|
pk845:
2018-07-14 20:04:54
given Time Limit is 1sec but my code gives AC with 3.1 sec. Why??
|
|
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?
|
|
theph0enix:
2016-06-17 09:17:42
Slowest solution... 0.35s with bottom up O(n^2) space :(
|
|
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 |