Fișierul intrare/ieșire	ydist.in, ydist.out	Sursă	Lot Sovata 2014
Autor	Andrei Ciocan	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.15 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ydist (lot liceu)

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

Cerință

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.

Date de intrare

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

Date de ieșire

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

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, 1 000 000].
• 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.

Exemplu

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