Fişierul intrare/ieşire:mindist.in, mindist.outSursăLot Focsani 2016, Baraj 2 Seniori
AutorRadu VisanAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test4.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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, 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

Exemplu

mindist.inmindist.out
4
4 1
3 4
2 2
1 3
0
4
3
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?