oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

kayaking Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

kayaking.html

Little Joseph went kayaking in Pulau Ubin and he must visit a few nature spots. However, because of the high tide and the low tide, Little Joseph can only move right in the morning and left in the afternoon. He must start and end at his campsite (the campsite will always be the leftmost point). This means that Little Joseph has to start from the leftmost point and only move right all the way onto the rightmost point, and then return by only moving left all the way back to the leftmost point.

Given the coordinates of all the nature spots/campsite, what is the shortest distance the kayak must travel to complete the whole route? Note that the x coordinate of each point is unique.

Input

The first line contains an integer n, representing the number of points Little Joseph must visit (including the campsite)
The next n lines contain two integers representing the x and y coordinates of the point respectively.

Output

Print out the shortset distance the kayak must travel (print out to the NEAREST integer. If the answer is 2.7, you should print out 3)

Sample Input 1

7
0 0
1 6
2 3
5 2
6 5
7 1
8 4

Sample Output 1

26
[Explanation: The shortest route is moving from (0,0) to (2,3) to (5,2) to (7,1) to (8,4) to (6,5) to (1,6) and finally back to (0,0) giving a length of about 25.58, hence the answer is 26]

Limits

For 30% of the test cases, n<10
For 60% of the test cases, n<100
For 100% of the test cases, n<1000

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o kayaking -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.