A disaster-relief drone must fly over a flat coordinate grid and visit a list of rescue waypoints in the exact order given, starting from the first waypoint. Each second, the drone may shift its position by one unit along the x-axis, one unit along the y-axis, or one unit along both simultaneously (a diagonal step) — in other words, in a single second its x-coordinate may change by −1, 0, or +1 and, independently, its y-coordinate may also change by −1, 0, or +1 (it may also stay put, though that is never useful here). Moving directly from one waypoint to the next in this way takes exactly as many seconds as the larger of the horizontal and vertical distance between them.
Compute the minimum total number of seconds the drone needs to visit every waypoint in the given order.
The first line contains a single integer n, the number of waypoints. Each of the next n lines contains two integers x and y, the coordinates of one waypoint, given in visiting order.
Print a single integer: the minimum total number of seconds needed to visit all n waypoints in order.
Example 1
Input
3 1 1 3 4 -1 0
Expected
7
Explanation
From (1,1) to (3,4): the horizontal distance is 2 and the vertical distance is 3, so this leg costs max(2,3) = 3 seconds (2 diagonal steps handle both axes together, then 1 more vertical step). From (3,4) to (-1,0): the horizontal distance is 4 and the vertical distance is 4, so this leg costs max(4,4) = 4 seconds. Total time is 3 + 4 = 7.
Example 2
Input
2 3 2 -2 2
Expected
5
Explanation
From (3,2) to (-2,2): the horizontal distance is 5 and the vertical distance is 0, so the drone just moves straight along the x-axis, costing max(5,0) = 5 seconds. There are no more waypoints, so the total time is 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →