Délka čáry
Zadání
V rovině je dán trojúhelník T. Označme jeho vrcholy symboly A, B, C tak, aby pro jeho strany AB, BC, AC platilo |AB| ≤ |BC| ≤ |AC|.
Pro trojúhelník T definujeme další tři trojúhelníky T(1), T(2) a T(3) takto:
Uvnitř strany AC trojúhelníka T zvolíme body D a E tak, že platí |AD| = |DE| = |EC|. Vzniknou tak tři další trojúhelníky ABD, BCE, BDE.
Položíme T(1) = ABD, T(2) = BCE, T(3) = BDE.
Pro libovolný trojúhelník T v rovině a pro dané kladné reálné číslo p definujeme množinu trojúhelníků M(T, p) rekurzivně takto:
Pokud obvod T je menší nebo roven p, potom M(T, p) = {T}.
Pokud obvod T je větší než p, potom M(T, p) = M(T(1), p) ∪ M(T(2), p) ∪ M(T(3), p).
Délku množiny M(T, p) definujeme jako polovinu obvodu T zvětšenou o polovinu součtu obvodů všech prvků M(T, p).
Obr. 2. Příklad. A = [0, 0], B = [108, 144], C = [300, 0]. M(ABC, 420) = {ADF, DFG, BDG, BDE, BEH, EHI, CEI}. Délka M(ABC, 420) je 1375.10. |M(ABC, 420)| = 7.
Obr. 3. Od příkladu na Obr. 2 se množina M(ABC, 150) liší pouze hodnotou svého parametru p. Délka M(ABC, 150) je 2974.14. |M(ABC, 150)| = 47.
Úloha
Pro daný trojúhelník T a kladné číslo p máme určit mohutnost a délku množiny M(T, p).
Poznámka 1
Když všechny trojúhelníky v množině M(T, p) nakreslíme v měřítku do jednoho obrázku podobně jako v obrázcích na této stránce, můžeme neformálně říci, že délka M(T, p) je rovna součtu délek všech čar, které jsme nakreslili (pokud žádnou čáru nekreslíme vícekrát).
Poznámka 2
Pozorný čtenář (a jiný v tomto textu ani nepředpokládáme) si jistě všiml, že množina M(T, p) není definována jednoznačně v případě, když trojúhelník T má alespoň dvě své nejdelší strany shodné délky. Platí ale, a také lze snadno ukázat, že jak mohutnost tak i délka množiny M(T, p) jsou pro daný trojúhelník T a danou hodnotu p vždy stejné.
Vstup
Na vstupu je jeden textový řádek. Obsahuje souřadnice tří bodů v rovině určujících výchozí trojúhelník T a dále hodnotu parametru p. Každý bod je určen svou x-ovou a y-ovou souřadnicí, které jsou uvedeny v tomto pořadí. Všechny hodnoty jsou desetinná čísla, každá obsahuje desetinnou tečku a dvě desetinné číslice. Všechny údaje na řádku jsou navzájem odděleny jednou mezerou.
Každá souřadnice každého vrcholu trojúhelníka T leží v intervalu <0, 1000>, hodnota p leží v intervalu <0.01, 1000>.
Výstup
Na výstupu je jeden textový řádek, který obsahuje dva údaje oddělené mezerou. Prvním údajem je celé číslo (bez desetinné tečky a bez desetinných číslic) udávající mohutnost množiny M(T, p) pro vstupní hodnoty T a p. Druhý údaj je desetinné číslo udávající délku množiny M(T, p) zaokrouhlenou na dvě desetinná místa. Toto číslo obsahuje povinně desetinnou tečku a vždy i dvě desetinné číslice. Můžeme předpokládat, že mohutnost M(T, p) nepřekročí 2×106.
Výpočty s necelými čísly bývají snadno náchylné k nepřesnostem, drobné chyby se mohou akumulovat a ovlivňovat výsledek. Je proto vždy zapotřebí značné opatrnosti. Data této úlohy jsou volena tak, že obvod žádného prvku žádné množiny M(T, p) se od hodnoty p neliší méně než o 10−4.