Fişierul intrare/ieşire:puncte.in, puncte.outSursăBaraj ONI 2007
AutorMircea Bogdan PasoiAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.5 secLimită de memorie9216 kbytes
Scorul tăuN/ADificultateN/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.inpuncte.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)).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content