| Fişierul intrare/ieşire: | ajutor.in, ajutor.out | Sursă | ONI 2003 - baraj |
| Autor | Marius Andrei | Adăugată de |  Silviu-Ionut Ganceanu •silviug |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ajutor.out |
|---|---|
| 4 4 1 1 5 5 1 5 5 1 0 0 1 1 3 3 4 1 | 2 0 4 1 |
