L - Lezecká stena

Časový limit: 8s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Dedko Jozef postavil svojim vnúčatám na dvore lezeckú stenu s plastovými úchytmi. Pri stavbe sa poriadne natrápil, tak chce lezeckú stenu chrániť čo najviac proti poveternostným vplyvom - najmä dažďu a snehu.
Rozhodol sa, že ju prikryje hliníkovým plechom, ktoré mu jeho syn v práci poohýba podľa potreby. Zoberie dostatočne široký plech a ním "obalí" lezeckú stenu tak, aby sa voda nikde nezadržiavala. Ľavá aj pravá strana budú zvislé a vrchná časť musí byť konvexná (ináč by tam stála voda/sneh).

Úloha

Pre daný popis rozmiestnenia úchytov na lezeckej stene vypočítajte dĺžku plechu potrebnú na prykrytie celej steny. Tento kryt má byť položený oboma koncami na zemi (Y-ová súradnica má hodnotu 0).

Vstup

V prvom riadku vstupu sa nachádza počet úchytov N. Nasleduje N riadkov, každý s dvoma celočíselnými súradnicami X, Y ďalšieho úchytu (Y určuje výšku).
1 ≤ N ≤ 500 000
0 ≤ X, Y ≤ 1 000 000

Výstup

Výstupom programu je dĺžka plechu potrebná na zakrytie danej lezeckej steny vyjadrená s presnosťou na (aspoň) 3 desatinné miesta.

Príklad

Na obrázku je znázornená lezecká stena so šiestimi úchytmi.

Vstup:

Výstup:

231.0469

Dĺžka jednotlivých častí plechu (podľa ohnutia, zľava zdola) sú 60, 64.03124, 32.01562, 75.

UPJŠ ŠVK 2014