Runda 17 [Hard] - Rysunki

28.03.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 17; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Rysunki

Tomek zawsze ma świetny pomysł na prezenty dla znajomych. Tak się składa, że niebawem kilku jego przyjaciół obchodzi urodziny. Wpadł na pomysł podarowania im pięknych dzieł sztuki - wielokątnych kawałków różowego marmuru z Krety. Każdy taki prezent ma kształt wielokąta prostego (bez samoprzecięć, z niezerowym polem), w dodatku daje się tak umieścić na płaszczyźnie, że jego wierzchołki znajdują się w punktach o współrzędnych całkowitych.

Tomek chce najpierw zrobić projekty prezentów, nim zabierze się do dzieła. Narysował jeden wielokąt, po czym doszedł do wniosku, że dobrze byłoby tak dobrać pozostałe prezenty, aby nikt nie czuł się pokrzywdzony, a zarazem każdy z jego przyjaciół poczuł się wyjątkowo. Postanowił więc, że wszystkie sporządzone plany będą przedstawiały wielokąty podobne do pierwszego narysowanego (wciąż z zachowaniem kształtu wielokąta prostego i współrzędnych całkowitych). Zauważmy, że dla każdego wielokąta istnieje dokładnie jeden wielokąt podobny (w tym sensie) o większym polu od niego, taki, że żaden inny mniejszy wielokąt nie ma tych własności (czyli w pewnym sensie "następnik", spójrz na ilustrację). Tomek zamierza wykonać $ k $ kolejnych wielokątów - narysowany na kartce, jego następnik, następnik następnika, itd. 

(poniżej wielokąt oraz jego następnik)

Czy pomożesz mu obliczyć, jak wiele marmuru potrzebuje aby stworzyć piękne dzieła sztuki dla przyjaciół? Na jeden wielokąt potrzeba tyle marmuru, ile wynosi wartość jego pola.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ n $ oraz $ k $ (odpowiednio liczbę wierzchołków narysowanego wielokąta oraz liczbę przyjaciół, których chce obdarować Tomek) ($ 3 \leq n \leq 10000, 1 \leq k \leq 10^{6} $). W kolejnych $ n $ liniach znajdują się pary liczb całkowitych $ x_{i}, y_{i} $ - współrzędnych kolejnych wierzchołków wielokąta. (Pierwszy połączony z drugim, drugi z trzecim, ..., $ n $-ty z pierwszym). Wartości bezwględne współrzędnych są ograniczone przez $ 10^{6} $. Wierzchołki mogą być podane w kolejności zgodnej z ruchem wskazówek zegara, bądź przeciwnej do niej. Żadne trzy kolejne wierzchołki nie będą współliniowe.

Wyjście:

Jedyna liczba na wyjściu powinna oznaczać sumę pól wielokątów - prezentów dla $ k $ przyjaciół Tomka - z dokładnie jedną cyfrą po przecinku. Możesz założyć, że ta suma nie będzie wieksza niż $ 10^{15} $.

Przykład:

Wejście:

4 3
1 1
1 4
7 4
4 1

Wyjście:

75.0

Kolejne wielokąty mają pola 13.5, 24 oraz 37.5.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasRysunki
1Damian Straszak1002:14:3610
2Wojtek Nadara1003:06:5910
3Arek Wróbel1040:00:5710
4Bartłomiej Gajewski1065:44:5610
5Wojciech Szałapski10105:32:2710
6Piotr Bejda10148:10:3310
7Witold Długosz10182:35:1710
8Krzysztof Pszeniczny905:39:109
9Krzysztof Drab786:26:197
10Przemysław Derengowski4174:53:524
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com