== 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.
Poveste şi cerinţă...
h2. Date de intrare
Pe prima linie a fisierului de intrare $mindist.in$ se va afla $N$, numărul de puncte.
Urmează $N$ linii, pe linia $i$ se vor afla coordonatele întregi $x[i] y[i]$ ale celui de-al $i$-lea punct inserat.
Fişierul de intrare $mindist.in$ ...
h2. Date de ieşire
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.
În fişierul de ieşire $mindist.out$ ...
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$
* $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") ==
