Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | mindist.in, mindist.out | Sursă | Lot Focsani 2016, Baraj 2 Seniori |
| Autor | Radu Visan | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 2.25 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mindist
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.
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.
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.
Restricţii
Răspunsul pentru punctul primul punct, d1, 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
Exemplu
| mindist.in | mindist.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
