Fişierul intrare/ieşire:	dist3.in, dist3.out	Sursă	ad-hoc
Autor		Adăugată de	CCEX2015 •CCEX2015
Timp execuţie pe test	1.5 sec	Limită de memorie	100000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dist3

Fie N puncte în planul bidimensional. Costul deplasării între două puncte P(x1, y1) şi Q(x2, y2) este definit prin expresia min(|x1 - x2|, |y1 - y2|). Se cere să se găseasca costul minim al unui drum care începe în punctul 1 şi se termină în punctul N.

Date de intrare

Fişierul de intrare dist3.in va conţine pe prima sa linie numărul N, reprezentând numărul de puncte. Urmează N linii, fiecare conţinând câte o pereche de numere întregi (X[i], Y[i]), reprezentând coordonatele punctelor, în ordine.

Date de ieşire

În fişierul de ieşire dist3.out va conţine pe unica sa linie răspunsul cerut, costul minim al unui drum care începe în punctul 1 şi se termină în punctul N.

Restricţii

• 1 ≤ N ≤ 200.000
• 0 ≤ X[i], Y[i] ≤ 10⁹
• Pentru teste în valoare de 50 de puncte, are loc în plus restricţia 1 ≤ N ≤ 100

Exemplu

Explicaţie

Ruta 1 -> 2 -> 4 are costul 1 + 0 = 1.

Cum se trimit solutii?