Fişierul intrare/ieşire:ydist.in, ydist.outSursăLot Sovata 2014 Seniori Baraj 3
AutorAndrei CiocanAdăugată dedariusdariusMarian Darius dariusdarius
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.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

Cum se trimit solutii?