Fişierul intrare/ieşire:ajutor.in, ajutor.outSursăONI 2003 - baraj
AutorMarius AndreiAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ajutor

Dacă te-ai rănit, nu folosi Sprite să tratezi rana. Cel mai bine e să fugi la cel mai apropiat post de prim ajutor. Norocul tău este că ai o hartă din care poţi afla coordonatele carteziene ale posturilor de prim ajutor. Ghinionul este că, din cauza durerii, nu poţi să fugi direct spre un post, ci numai pe direcţiile nord-sud şi est-vest. Ca să ştii dacă mai are sens să fugi spre un post sau să te bucuri de ultimele clipe de viaţă, cel mai bine e să evaluezi distanţa până la cel mai apropiat post de prim ajutor. Cel mai apropiat post este cel pentru care distanţa Manhattan este minimă.

De data aceasta ai scăpat pentru că timpul necesar ajungerii până la post a fost suficient; însă îţi pui întrebarea: dacă accidentul s-ar fi întâmplat în alt loc, ai fi scăpat?

Cerinţă

Se consideră N puncte in plan, reprezentând posturile de prim ajutor şi alte M puncte reprezentând posibile locaţii ale accidentului. Se cere pentru fiecare dintre cele M puncte distanţa Manhattan până la cel mai apropiat post.

Date de intrare

Fişierul de intrare ajutor.in conţine pe prima linie numerele întregi N şi M, în acestă ordine, separate printr-un spaţiu. Pe următoarele N linii se află câte două numere întregi, separate printr-un spaţiu, reprezentând coordonatele fiecărui post de prim ajutor. Pe următoarele M linii se află câte două numere intregi, separate printr-un spaţiu, reprezentând coordonatele punctelor de accident. Coordonatele se dau în ordinea (abscisa, ordonata).

Date de ieşire

În fişierul de ieşire ajutor.out va conţine M linii, cu câte un număr pe fiecare linie, reprezentând distanţa minimă până la cel mai apropiat post de prim ajutor.

Restricţii şi precizări

  • 1 ≤ N ≤ 400
  • 1 ≤ M ≤ 500000
  • oricare coodonată este un număr întreg din intervalul [0,32000]
  • Dacă te afli deja la un post de prim ajutor (coordonatele sunt identice) distanţa e 0.
  • Distanţa Manhattan este cel mai scurt drum între două puncte, mergând doar pe direcţii paralele cu axele de coordonate, adică |x1-x2|+|y1-y2|, unde (x1,y1), (x2,y2) sunt coordonatele celor 2 puncte.
  • În fişierul de intrare pot exista puncte cu aceleaşi coordonate.
  • Se acordă punctele pentru fiecare test, doar dacă toate valorile din fişierul de ieşire sunt corecte.

Exemplu

ajutor.inajutor.out
4 4
1 1
5 5
1 5
5 1
0 0
1 1
3 3
4 1
2
0
4
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content