Balóny

Aký veľký môžeme nafúknuť balón na $x$-ovej súradnici $x_2$, aby sa dotýkal balónu s polomerom $r_1$ na súradnici $x_1$? Dva balony

\begin{align*} |S_1S_2|^2 & = |S_1X|^2 + |XS_2|^2 \\ (r_1+r_2)^2 & = (r_1-r_2)^2 + (x_2-x_1)^2 \\ \underline{r_1^2}+2r_1r_2+\underline{r_2^2} & = \underline{r_1^2}-2r_1r_2+\underline{r_2^2}+ (x_2-x_1)^2\\ 4r_1r_2 & = (x_2-x_1)^2 \\ r_2 & = \textbf{?} \\ r_2 & \leq \frac{(x_2-x_1)^2}{4r_1} \\ \end{align*}

Ako je to s viacerými balónmi? Ktorých balónov sa môže dotýkať zelený balón (ktorý aktuálne nafukujeme)? Viacero balonov

  • počítajte s najvyššou presnosťou (nezaokrúhľujte ani počas výpočtu ani vo výpise)
  • pridávame balón s polomerom $min(r, r_{\texttt{dotyk}})$
  • stačí si pamätať klesajúcu postupnosť balónov od začiatku, pri pridaní ďalšieho sa menšie zakryjú, teda zo zoznamu (zásobníka) môžeme odstrániť ... multipop zásobník, a teda časová zložitosť $\Theta(n)$

1 akceptované riešenie za plný počet bodov

  • 4.33 s (Java)

Doska plošných spojov

4 body do 14.04.2020 12:00
2 body do 21.04.2020 12:00