Délka čáry

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.

Obr. 1 Příklad. Trojúhelník T = ABC a trojúhelníky T(1), T(2), T(3).

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×10⁶.
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⁻⁴.

Příklad 1

Vstup:

0.00 0.00 300.00 0.00 108.00 144.00 420.00

Výstup:

7 1375.10

Tento příklad je zobrazen na Obr. 2 výše.

Příklad 2

Vstup:

0.00 0.00 300.00 0.00 108.00 144.00 150.00

Výstup:

47 2974.14

Tento příklad je zobrazen na Obr. 3 výše.

Příklad 3

Vstup:

10.00 10.00 600.00 10.00 630.28 412.01 40.9

Výstup:

3827 56396.40

Tento příklad je zobrazen níže na Obr. 4.

Obr. 4 Schéma M(T, p) z příkladu 3.

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data