Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ydist.in, ydist.out | Sursă | Lot Sovata 2014 Seniori Baraj 3 |
| Autor | Andrei Ciocan | Adăugată de |  Marian Darius •dariusdarius |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ydist
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ă).
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.
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, 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.
Exemplu
| ydist.in | ydist.out |
|---|---|
| 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 |
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).
