== include(page="template/taskheader" task_id="ydist") ==
Poveste şi cerinţă...
Prinţesa cu ochii verzi, Rafaela, a decis că este timpul să renunţe la problemele regatului şi să se joace. Astfel, ea are $N$ bile punctiforme (reprezentate de $N$ puncte în planul cartezian) şi $Q$ drepte care trec prin originea sistemului de coordonate. Pentru fiecare dintre cele $Q$ drepte, se întreabă care ar fi prima bilă dintre cele $N$ care ar lovi dreapta dacă bilele ar începe simultan să cadă (perpendicular pe axa Ox, cu aceeaşi viteză).
h2. Cerinta
Dându-se $N$ puncte în plan şi $Q$ drepte (de query), Rafaela se întreabă care ar fi distanţa minimă (pe axa Oy) de la puncte la fiecare dreaptă. Voi trebuie să afişaţi în fişierul de ieşire răspunsul pentru fiecare dintre cele $Q$ drepte.
h2. Date de intrare
Fişierul de intrare $ydist.in$ ...
Fişierul de intrare $ydist.in$ conţine pe prima linie două numere naturale $N$ şi $Q$, separate prin câte un spaţiu, reprezentând numărul de puncte din plan, respectiv numărul de drepte de query. Pe următoarele $N$ linii urmează câte două numere naturale $x$ şi $y$, separate prin câte un spaţiu, reprezentând coordonatele punctelor în planul cartezian. Pe următoarele $Q$ linii urmează câte două numere naturale $a$ şi $b$, separate prin câte un spaţiu, reprezentând coordonatele celui de-al doilea punct prin care trece dreapta de query (primul fiind $(0, 0)$, al doilea $(a, b)$).
h2. Date de ieşire
În fişierul de ieşire $ydist.out$ ...
Fişierul de ieşire $ydist.out$ va conţine $Q$ linii, pe fiecare linie aflându-se un singur număr real, reprezentând distanţa minimă (pe axa Oy) de la puncte la dreapta de query respectivă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$
* Coordonatele $x$ şi $y$ ale tuturor punctelor din fişierul de intrare se află în intervalul $[1, 1000000]$.
* Rezultatul se consideră corect dacă valoarea absolută a diferenţei între acesta şi rezultatul comisiei este mai mică decât $0.00001$.
* Se garantează că există cel puţin o bilă deasupra fiecărei drepte.
h2. Exemplu
table(example). |_. ydist.in |_. ydist.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 3
14 20
4 4
6 6
7 15
5 2
1 20
19 16
5 18
2 4
17 6
| 16.4
1
0.235294117647059
|
h3. Explicaţie
...
Prima dreapta de query este: $(0, 0) -> (5, 18)$, iar disţanta minimă (pe axa Oy) este dată de punctul: $(1, 20)$.
A doua dreaptă de query este: $(0, 0) -> (2, 4)$, iar distanţa minimă (pe axa Oy) este dată de punctul: $(7, 15)$.
A treia dreaptă de query este: $(0, 0) -> (17, 6)$, iar distanţa minimă (pe axa Oy) este dată de punctul: $(5, 2)$.
== include(page="template/taskfooter" task_id="ydist") ==
