Demi-finale 2010, épreuve machine - Fête foraine

DIFFICULTE

LIMITE DE MEMOIRE

4096 ko

LIMITE DE TEMPS

3000 ms

ÉNONCÉ

Aujourd'hui, Joseph Marchand décide de se détendre un peu, il prend donc le chemin de la fête foraine qui s'est installée près de chez lui.

Ce parc d'attraction a une organisation un peu spéciale, on ne peut acheter les tickets que un par un et toujours au même endroit, au guichet. Comme Joseph est fainéant, il voudrait connaître la distance minimale qu'il devra parcourir pour faire une fois chaque attraction.

La route qui mène à une attraction est forcément parallèle à l'axe des abscisses ou des ordonnées et est sans obstacle.

ENTRÉE

• Deux entiers Xg et Yg : les coordonnées du guichet.
• Un entier N : le nombre d'attractions.
• Deux entiers X et Y : les coordonnées de l'attraction, répétées N fois.

LIMITES

• 0 <= Xg <= 50
• 0 <= Yg <= 50
• 0 <= N <= 215000
• 0 <= X <= 10000
• 0 <= Y <= 10000

SORTIE

• Un entier représentant la distance parcourue par Joseph Marchand.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

0
0
2
1 1
3 4

11