Fişierul intrare/ieşire:ydist.in, ydist.outSursăLot Sovata 2014
AutorAndrei CiocanAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici