Úloha 3.u3: Chodníčky v parku (3 b)

Zadáno v čísle 22.3.

Řešeno v čísle 22.5.

Zadání

Ve městě je obdélníkový park a tímto parkem teče potůček. Po obou březích vedou chodníčky, ale nikde v parku přes potůček nevede most. Oba chodníčky vedou stále právě 2.5 m daleko od středu potůčku. Potůček do parku vtéká na jihu (kolmo na okraj parku), v parku se nějak klikatí a poté vytéká směrem na západ (opět kolmo na okraj parku). Klikatění potůčku dostanete na vstupu jako posloupnost rovných úseků – popsaných jejich délkou – a zatáček – popsaných poloměrem zakřivení potůčku a úhlem, o který je potůček zakřiven (kladné číslo představuje zatáčku do prava, záporné do leva). Napište program nebo popište algoritmus s co nejmenší časovou složitostí, který vypíše, po kterém břehu a o kolik metrů je cesta podél potůčku kratší.

Můžete předpokládat, že trasa potůčku v parku je rozumná, tedy potůček:

  • nikdy neprotíná sám sebe ani se nepřibližuje sám k sobě na méně než 5 m
  • nikdy neopisuje oblouk s poloměrem menším než 2.5 m
  • nikde mimo začátek a konec svého průtoku parkem se nepřibližuje na méně než 2.5 m k okraji parku

Řešení

Na rovných úsecích se délky chodníčků nijak neliší, budou nás tedy zajímat jen zatáčky. Když potůček zatočí doprava s poloměrem $r$ o úhel $\alpha $ (v radiánech), délky chodníčků vzdálených stále $d = 2{,}5 \, \mathrm{m}$ od středu potůčku budou v tomto úseku rovny

\[ 2 \pi (r + d) {\alpha \over 2 \pi } = \alpha (r + d) \]

na levém břehu a

\[ 2 \pi (r - d) {\alpha \over 2 \pi } = \alpha (r - d) \]

na pravém. Jejich rozdíl pak bude

\[ \alpha (r + d) - \alpha (r - d) = \alpha (r + d - r + d) = 2d \alpha . \]

Vidíme, že rozdíl nezávisí na poloměru zatáčky, nýbrž jen na jejím úhlu. Navíc vyjde stejně, i pokud potůček zatáčí doleva (lišit se budou jen ve znaménku schovaném v $\alpha $). Protože potůček vtéká do parku kolmo na východě, vytéká kolmo na severu a nikde se nekříží, nasčítají se úhly všech $n$ zatáček na $\pi / 2$ (neboli pravý úhel). Celkový rozdíl délek je pak

\[ \sum _{i=1}^ n 2d\alpha _ i = 2d \sum _{i=1}^ n \alpha _ i = 5 {\pi \over 2} \, \mathrm{m} \]

(přibližně 7,85 m), o tolik je delší chodníček na levém břehu. Náš „algoritmus“ se tedy vůbec nebude dívat na popis úseků, jen v konstantním čase vypíše tento výsledek.

Matěj