Zadanie

Poznáte Goldbergove stroje, všakže? Ak nie, tak v krátkosti: Goldbergov stroj je zariadenie, ktoré jednoduchú vec vykonáva najzložitejším možným spôsobom. Adam práve na jednom takom pracuje. Jeho stroj má jedinú úlohu: dostať loptičku do pohárika. Zadanie je síce jednoduché, jeho plnenie však musí mať dej.

Jednou z hlavných a najpremakanejších častí tohto stroja je horská dráha. Loptička (po už aj tak dosť dlhej ceste kadejakými inými časťami) spadne do akéhosi baníckeho vozíčka podobného tomu z Minecraftu, ktorý sa následkom toho pohne a začne jazdiť po dráhe. Adam nemá dosť peňazí na elektrický vozík, a tak sa tento pohybuje iba pomocou gravitácie a zotrvačnosti.

Horská dráha však nie je jediná súčasť Adamovho veľkolepého Goldbergovho stroja. Preto potrebuje vedieť, za aký čas prejde loptička celou dráhou, aby mohol v správnom čase spustiť ostatné časti.

Úloha

Dráha je zadaná ako lomená čiara. Na začiatku sa banícky vozík aj s loptičkou nachádza na prvom bode tejto čiary a má nulovú rýchlosť. Vozík sa následkom gravitácie začne hýbať po dráhe. Na každom zlomovom bode vozík zmení smer pohybu a adekvátne k tomu aj rýchlosť. Medzi vozíkom a dráhou nie je žiadne trenie a celá sústava sa riadi bežnými zákonmi Newtonovskej fyziky.

Vždy keď sa vozík dostane na zlom dvoch úsečiek lomenej čiary, použije sa bežný zákon zotrvačnosti a z jeho rýchlosti sa zachová zložka v smere nasledujúcej úsečky. (Napríklad, ak koľajnice zabočia o 90 alebo viac stupňov, vozík sa zastaví a zachrániť ho môže už len gravitácia. Ak koľajnice zabočia o 60 stupňov, rýchlosť vozíka sa zníži na polovicu. A tak podobne.)

Vašou úlohou je vypočítať, za aký čas prejde vozík s loptičkou celou horskou dráhou (skrátka, kedy dosiahne posledný bod lomenej čiary). Ak vozík nikdy neprejde celou dráhou, vypíšte NEVER.

Formát vstupu

Na prvom riadku sa nachádza veľkosť gravitačného zrýchlenia \(g\) (reálne číslo) na osi \(y\) (zrýchlenie na osi \(x\) je vždy nulové). Platí, že \(-100.0 \leq g \leq +100.0\).

Na druhom riadku sa nachádza počet bodov lomenej čiary \(2 \leq n \leq 100\).

Na ďalších \(n\) riadkoch sa nachádzajú celočíselné súradnice jednotlivých bodov lomenej čiary \(-10^9 \leq x_i, y_i \leq +10^9\).

Formát výstupu

Vypíšte jeden riadok a na ňom jedno reálne číslo: čas, za ktorý loptička prejde celou horskou dráhou na Adamovom Goldbergovom stroji. Absolútna alebo relatívna odchýlka od nášho výsledku môže byť najviac \(10^{-6}\). V prípade, že loptička nikdy neprejde celou dráhou vypíšte jeden riadok a na ňom text NEVER.

Príklad

Input:

9.81
3
0 0
0 5
10 6

Output:

4.648720407500884

Input:

-9.81
3
0 0
0 5
10 6

Output:

NEVER

Input:

3.1415
4
-2 0
2 1
-2 2
2 3

Output:

9.869432502176037

Táto úloha nebola veľmi ťažká, bolo treba vedieť základy mechaniky a dať si pozor na aritmetické zákernosti ako je delenie nulou, odmocňovanie záporného čísla a podobne.

Úloha sa riešila takto: ak sa vozík nachádza na začiatku nejakej úsečky (priamo na jej začiatočnom bode) a vieme, akou rýchlosťou a v ktorom smere sa hýbe, aký je sklon danej úsečky a aká je dlhá, tak vieme vypočítať, ako dlho bude vozíku trvať, kým prejde celou úsečkou, a tiež, ako rýchlo (a či vôbec) sa bude hýbať na jej konci.

Troška fyziky

Povedzme, že úsečka je sklonená pod uhlom \(\alpha\) a má dĺžku \(d\). (V skutočnosti nebudeme potrebovať vedieť presný uhol \(\alpha\), ale iba \(\sin \alpha\) a \(\cos \alpha\). Kosínus uhla zvieraného dvoma vektormi sa ľahko vypočíta ako podiel ich skalárneho súčinu a súčinu ich veľkostí. Sínus sa vypočíta ako podiel ich vektorového súčinu a súčinu ich veľkostí.) Ďalej povedzme, že vozík sa hýbe rýchlosťou \(v\) smerom k jej druhému koncovému bodu (čiže \(v\) je len nezáporné reálne číslo, vektor rýchlosti vozíka vieme vyrátať ako \((v \cdot \cos \alpha, v \cdot \sin \alpha)\)).

Úsečka, po ktorej sa vozík bude hýbať je vlastne naklonená rovina. Pohyb po naklonenej rovine je istý druh zrýchleného pohybu, v ktorom sa zrýchlenie dá odvodiť od gravitačného zrýchlenia a sklonu naklonenej roviny. Oba parametre poznáme, preto zrýchlenie môžeme vypočítať ako:

\[ a = g \cdot \sin \alpha \]

Je dôležité si uvedomiť, že podľa toho, či rovina klesá alebo stúpa bude zrýchlenie kladné alebo záporne. Ak je rovina vodorovná, zrýchlenie bude nulové.

Teraz nám už len zostáva vyrátať, za aký čas prejde vozík danou úsečkou a akú rýchlosť bude mať na jej konci. To, ako rýchlo sa bude hýbať vieme vypočítať jednoducho z času prejdenia, keďže po celý čas bude vozík rovnomerne akcelerovať zrýchlením \(a\).

Ako vypočítame čas, za ktorý vozík prejde celou úsečkou? Z fyziky vieme vzťah medzi počiatočnou rýchlosťou \(v_0\), rovnomerným zrýchlením \(a\), časom \(t\) a dráhou \(s\):

\[ s = v_0 t + \frac{1}{2} a t^2 \]

V našom prípade chceme, aby vozík prešiel celou úsečkou – musí teda prejsť dráhou dĺžky \(d\). Tiež vieme, že počiatočná rýchlosť nášho vozíka je \(v\), dosadíme teda tieto hodnoty do vzorca:

\[ d = v t + \frac{1}{2} a t^2 \]

Neznáma, ktorú z tohto vzorca potrebujeme vypočítať je \(t\). Vidíme, že vzhľadom na \(t\) je toto kvadratická rovnica. Pomocou klasického vzorca s diskriminantom dostaneme dve možné riešenia:

\[ D = 2 a d + v^2 \] \[ t_1 = (-\sqrt{D} - v) / a \] \[ t_2 = (\sqrt{D} - v) / a \]

Prečo sú však riešenia dve? Predstavme si, že namiesto úsečky máme polpriamku a táto polpriamka stúpa (akcelerácia je teda záporná). Pokiaľ sa vozík hýbe dostatočne rýchlo, môže prejsť po priamke dĺžku \(d\). Čas, v ktorom dosiahne tento bod na priamke je prvé riešenie našej kvadratickej rovnice.

Následne bude vozík ešte chvíľu stúpať, zastaví sa a začne zrýchľovať opačným smerom. Bodom, ktorý je od počiatočnej pozície vozíka vzdialený \(d\) prejde vozík opäť, tentoraz z opačnej strany. Čas, v ktorom sa to stane je druhé riešenie našej kvadratickej rovnice.

Môže sa dokonca stať, že niektoré riešenie tejto rovnice bude záporné, čo znamená, že vozík prešiel daným bodom “v minulosti”.

Pri riešení tejto kvadratickej rovnice si treba dať pozor na viacero vecí.

Prvá je, že diskriminant môže byť záporný. Ak sa to stane, znamená to, že vozík nikdy nedosiahne koniec úsečky, a teda môžeme vypísať NEVER.

Druhá vecou je prípad, kedy je akcelerácia nulová. Všimnime si, že v takom prípade by sme delili nulou a teda horeuvedené vzorce nebudú použiteľné. To však vôbec nie je problém, ak je \(a = 0\), tak pôvodná rovnica prejdenej vzdialenosti sa dá zjednodušiť na:

\[ d = v t \]

Z čoho si vieme čas odvodiť veľmi jednoducho:

\[ t = \frac{d}{v} \]

Aj tu si však musíme dať pozor na prípad kedy \(v = 0\). Vtedy opäť vypíšeme NEVER.

Výber správneho riešenia

Keď už sme ošetrili všetky veci, na ktoré si treba dať pozor, získame dve riešenia: \(t_1\) a \(t_2\). Ktoré je to správne? Záporné riešenia to určite nebudú a z tých nezáporných treba vybrať to najmenšie, keďže to je čas, kedy sa vozík prvý krát dotkne druhého bodu úsečky. Pokiaľ sú obe riešenia záporné, vozík sa do tohto bodu nedostane.

Zachovanie rýchlosti

Na to, aby sme vedeli vyššie spomenuté hodnoty rátať aj pre nasledujúce úsečky ešte potrebujeme zistiť, akú rýchlosť bude vozík mať na konci aktuálnej úsečky, a o koľko spomalí (prípadne zrýchli) keď narazí na ich zlom.

Rýchlosť na konci úsečky vieme vyrátať ľahko z počiatočnej rýchlosti a rovnomerného zrýchlenia, ktoré už máme.

\[ v_1 = v + a t \]

Keďže medzi dvomi úsečkami je zlom, z tejto rýchlosti sa pri prechode na ďalšiu úsečku zachová len časť, konkrétne zložka zodpovedajúca smeru ďalšej úsečky. Označme si vzájomný uhol medzi oboma úsečkami ako \(\theta\). Potom rýchlosť, ktorá sa zachová vypočítame, ako:

\[ v_2 = v_1 \cos \theta \]

(Ak celkom nerozumiete, prečo zachovanú rýchlosť vypočítame takto, odporúčame si to nakresliť.)

Ak dostaneme zápornú \(v_2\), znamená to, že vozík narazil na ostrý zlom. Na takomto zlome sa nezachováva žiadna rýchlosť, preto v takomto prípade nastavíme \(v_2\) na nulu.

Všetko spolu

Keď už vieme počítať všetky veci popísané vyššie, postupne prejdeme všetky úsečky, posčítavame všetky časy a nakoniec vypíšeme celkový čas. Ak počas prechádzania úsečkami zistíme, že niektorou z nich už vozík neprejde, tak vypíšeme NEVER a skončíme.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.