puncte

Puncte

== include(page="template/taskheader" task_id="puncte") ==

Poveste si cerinta...

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 ({$x{~1~},y{~1~}$}) si ({$x{~2~},y{~2~}$}) este {$(x{~1~}-x{~2~})^2^+(y{~1~}-y{~2~})^2^$}.
 
h2. 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.

h2. 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.

h2. 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).

h2. 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$}.

h2. Exemplu
table(example). |_. puncte.in |_. puncte.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 2
1 1
5 1
10 2
2
7
| 2
5

|
h3. 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$})).

== include(page="template/taskfooter" task_id="puncte") ==