dist3

Dist3

== include(page="template/taskheader" task_id="dist3") ==

Poveste şi cerinţă...

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$.

h2. Date de intrare

Fişierul de intrare $dist3.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $dist3.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. dist3.in |_. dist3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|4
0 0
6 1
5 5
6 6
| 1
|

h3. Explicaţie

...

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

== include(page="template/taskfooter" task_id="dist3") ==