MTHERMES - IOI04 Hermes

no tags 

In a modern city for Greek gods, the streets are geometrically arranged as a grid with integer coordinates with streets parallel to the x and y axes. For each integer value Z, there is a horizontal street at y=Z and a vertical street at x=Z. This way, integer coordinate pairs represent the street junctions. During the hot days, the gods rest in cafeterias at street junctions. Messenger Hermes is to send photon messages to gods resting in the cafeterias by only moving along the city streets. Each message is for a single god, and it does not matter if the other gods see the message.

The messages are to be sent in a given order, and Hermes is provided the coordinates of the cafeterias in that order. Hermes starts from (0,0). To send a message to a cafeteria at (Xi,Yi), Hermes only needs to visit some point on the same horizontal street (with y-coordinate Yi) or on the same vertical street (with x-coordinate Xi). Having sent all of the messages, Hermes stops.

You are to write a program that, given a sequence of cafeterias, finds the minimum total distance Hermes needs to travel to send the messages.

INPUT

The first line contains one integer N: the number of messages to be sent. The following N lines contain the coordinates of the N street junctions where the messages are to be sent. These N lines are in the order in which the messages are to be sent. Each of these N lines contains two integers: first the x-coordinate and then the y-coordinate of the street junction.

OUTPUT

The file is to contain a single line containing one integer: the minimum total distance Hermes needs to travel to send the messages.

EXAMPLE INPUT AND OUTPUT

Input
5
8 3
7 -7
8 1
-2 1
6 -5

Output
11

CONSTRAINTS

In all inputs, 1≤N≤20000, -1000≤Xi,Yi ≤1000. Additionally, in 50% of the inputs, 1≤N≤80.


hide comments
Mitch Schwartz: 2016-01-23 18:00:16

Moved to partial because of scoring.

(To be in classical, binary scoring is required. Note that with binary scoring it is still possible to give details about e.g. passing rate and cause of failure, if you know how to write judges.)

Last edit: 2016-01-23 18:08:57
Alex Anderson: 2015-11-14 03:10:07

Request for judge: Please have submissions which are not 100% marked as wrong (everything is marked as AC now).

Alex Anderson: 2015-11-14 03:08:51

@others

My guess is that it displays % of test cases you pass, and gives you the basic explanation of the first one you got wrong.

RADHE SHYAM LODHI: 2015-11-13 13:46:07

yes, plz clear how the output come?

Ray Brish Bhanu: 2015-11-13 10:31:15

plz explain how theoutput has been evaluated


Added by:Đặng Minh Tiến
Date:2015-11-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:CBT