Fişierul intrare/ieşire:gorilla.in, gorilla.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.125 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gorilla

Poate va amintiti de vechiul joc in QBasic, gorilla.bas. In caz ca nu va amintiti, jocul era despre 2 gorile care aruncau banane explozive una intr-alta. Fiecare gorila era controlata de unul din cei 2 jucatori. Fiecare jucator putea alege unghiul si viteza aruncarii, iar banana urma o traiectorie parabolica. Ca si cum gasirea unghiului si vitezei potrivite pentru a lovi gorila adversarului nu era destul de greu, in joc existau de asemenea si niste cladiri, care puteau bloca traiectoria bananei.

De data aceasta va aflati aproape de sfarsitul unui joc unde, din intamplare, ambele gorile au fost localizate la aceeasi inaltime (egala cu 0). Pentru a fi mai exacti, gorila dumneavostra este un punct localizat la coordonatele (0,0), oar gorila adversarului este un punct localizat la coordonatele (d,0). Intre cele 2 gorile exista N cladiri (segmente verticale) care au diverse inaltimi. Dumneavoastra doriti sa terminati jocul cat mai repede, astfel ca aruncarea urmatoare vreti sa fie ultima. Prin urmare, banana (care este tot un punct) trebuie aruncata in asemenea fel incat sa loveasca gorila adversarului, dar nu si cladirile (desi poate atinge varful oricarei cladiri). Mai mult, pentru a va etala calitatile superioare adversarului dumneavoastra, doriti ca viteza v cu care aruncati banana sa fie minima (dar puteti alege orice unghi intre 0 si ).

Cand veti rezolva aceasta problema, veti folosi valoarea acceleratiei gravitationale g (data in fisierul de intrare), precum si urmatoarele legi de miscare:

Date de intrare

Prima linie a fisierului de intrare gorilla.in contine un numar intreg T, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 3 numere, separate prin spatii: un numar intreg d, un numar real g si un numar intreg N. A i-a din urmatoarele N linii contine 2 numere intregi, separate printr-un spatiu: Xi si Hi. Xi este coordonata X a celei de-a i-a cladiri, iar Hi este inaltimea acesteia. In plus, Xi < Xi+1.

Date de iesire

Pentru fiecare din cele T teste, in ordinea din fisierul de intrare, afisati in fisierul de iesire gorilla.out cate o linie continand valoarea minima a vitezei necesare pentru a arunca banana. Afisati aceasta valoare cu 3 zecimale, rotunjite (in sus sau in jos) in functie de a patra zecimala.

Restrictii

  • 1 ≤ T ≤ 10
  • 0 ≤ g ≤ 10
  • 1 ≤ d ≤ 1 000 000
  • 0 ≤ N ≤ 50 000
  • 1 ≤ Xi < d
  • 1 ≤ Hi ≤ 1 000 000

Exemplu

gorilla.ingorilla.out
2
1 9.8 0
1000 1 1
500 10000
3.130
141.466
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content