| Fişierul intrare/ieşire: | puncte.in, puncte.out | Sursă | Baraj ONI 2007 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 9216 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Puncte
Zaharel a desenat pe o foaie de hartie N puncte in plan. Curios din fire, si-a ales inca M puncte pe axa Ox si s-a intrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanta minima). Se considera ca distanta dintre doua puncte (x1,y1) si (x2,y2) este (x1-x2)2+(y1-y2)2.
Cerinta
Scrieti un program pentru Zaharel care sa determine pentru fiecare dintre cele M puncte de pe axa Ox, care este distanta la cel mai apropiat punct dintre cele N desenate pe hartie.
Date de intrare
Fisierul de intrare puncte.in contine pe prima linie numerele naturale N, M separate prin spatii. Fiecare dintre urmatoarele N linii contine cate o pereche de numere naturale nenule x y, separate prin spatii, reprezentand coordonatele celor N puncte (in ordinea abscisa, ordonata). Fiecare dintre urmatoarele M linii contine cate un numar natural x, reprezentand abscisele (coordonatele pe axa Ox) ale celor M puncte.
Date de iesire
Fisierul de iesire puncte.out va contine M linii. Pe linia i va fi scris un numar natural reprezentand distanta la cel mai apropiat punct dintre cele N de pe hartie pentru al i-lea punct de pe axa Ox (considerand ordinea punctelor din fisierul de intrare).
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 200 000
- Toate coordonatele din fisierul de intrare sunt numere naturale din intervalul [1,109]
- Cele N puncte din fisierul de intrare sunt sortate dupa coordonata x crescator, iar in cazul in care doua puncte au aceeasi abscisa, ele sunt ordonate crescator dupa coordonata y.
- Pentru 50% din teste N ≥ 90 000 si M ≥ 150 000.
Exemplu
| puncte.in | puncte.out |
|---|---|
| 3 2 1 1 5 1 10 2 2 7 | 2 5 |
Explicatie
Pe hartie au fost desenate 3 puncte, avand coordonatele (1,1), (5,1), respectiv (10,2). Pe axa Ox se afla 2 puncte, avand abscisa 2, respectiv 7.
Distanta minima dintre punctul de pe axa Ox de abscisa 2 este 2 (cel mai apropiat punct fiind cel de coordonate (1,1)).
Distanta minima dintre punctul de pe axa Ox de abscisa 7 este 5 (cel mai apropiat punct fiind cel de coordonate (5,1)).
