Mindist

mindist

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

Se adaugă, pe rând, în plan, $N$ puncte de coordonate intregi. Pentru fiecare punct adăugat trebuie să găsiţi distanţa Manhattan minimă de la acel punct la oricare dintre punctele adăugate înaintea lui.

Se adaugă, pe rând, în plan, $N$ puncte.
Fiecare punct are coordonatele întregi.
Pentru fiecare punct adăugat trebuie să găsiţi distanţa Manhattan minimă de la acel punct la oricare dintre punctele adăugate înaintea lui.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $mindist.out$ va conţine $N$ linii.

Fişierul de ieşire mindist.out va conţine $N$ linii.

Pe linia $i$ se va afla un singur număr întreg, $d[i]$, care reprezintă distanţa Manhattan minimă de la punctul $i$ la oricare dintre punctele adăugate înaintea lui.
h2. Restricţii

* Răspunsul pentru punctul primul punct, @d[1]@, se consideră a fi $0$
* Distanţa Manhattan intre punctele $(x1, y1)$ şi $(x2, y2)$ este definită ca $|x1 – x2| + |y1 – y2|$
* Pentru $20%$ dintre teste, $N ≤ 150$
* Pentru restul de $80%$ dintre teste, $N ≤ 50 000$

* Răspunsul pentru punctul primul punct, $d[1]$, se consideră a fi $0$
* Distanţa Manhattan intre punctele (x1, y1) şi (x2, y2) este definită ca |x1 – x2| + |y1 – y2|
* Pentru 20% dintre teste, N ≤ 150
* Pentru restul de 80% dintre teste, N ≤ 50 000

* $1 ≤ x[i], y[i] ≤ 50 000$
h2. Exemplu
table(example). |_. mindist.in |_. mindist.out |

| 4
4 1
3 4
2 2
1 3
| 0
4
3
2
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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