Ziemniak [B]
Limit pamięci: 32 MB
Marcin obiera ziemniaka. Dla uproszczenia przyjmujemy, że ziemniak jest wielokątem
wypukłym1,
którego brzeg nazywamy skórką ziemniaka.
Marcin może wykonywać cięcia nożem. Przy każdym cięciu, Marcin wpierw wybiera prostą, wzdłuż której
będzie ciął. Następnie przecina ziemniaka wzdłuż tej prostej, po czym wyrzuca część ziemniaka, która znajduje
się po jednej ze stron prostej. Wyrzucone zostają także punkty ziemniaka znajdujące się na prostej cięcia, więc np.
cięcie wzdłuż prostej zawierającej bok oryginalnego ziemniaka ucina od ziemniaka samą jego skórkę znajdującą się na tym boku.
Ziemniak uznajemy za obrany, jeśli to, co z niego zostało, nie ma już żadnego punktu oryginalnej skórki.
Marcin chce się jak najmniej napracować, czyli obrać ziemniaka wykonując ograniczoną liczbę cięć
oraz uzyskując na koniec jak największy pozostały fragment ziemniaka.
Jakie największe pole obranego ziemniaka może uzyskać, wykonując co najwyżej cięć?
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis kartofla,
- wyznaczy największe możliwe do uzyskania pole pozostałej części pyry, zakładając możliwość
wykonania co najwyżej cięć,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite () oraz
(), oddzielone pojedynczym odstępem i
oznaczające liczbę wierzchołków wielokąta obrazującego ziemniaka oraz maksymalną
liczbę cięć, jakie chce wykonać Marcin w celu jego obrania.
Kolejne wierszy zawiera opisy kolejnych wierzchołków ziemniaka, w kolejności zgodnej z kierunkiem ruchu wskazówek zegara
lub przeciwnej do niego. Każdy taki wiersz zawiera dwie liczby całkowite i ,
, oznaczające współrzędne wierzchołka ziemniaka.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę rzeczywistą, zapisaną z dokładnie jedną
cyfrą po przecinku, oznaczającą największe możliwe do uzyskania pole ziemniaka obranego w co najwyżej cięciach.
Przykład
Dla danych wejściowych:
5 3
0 0
3 1
6 4
3 7
0 8
poprawną odpowiedzią jest:
24.0
Przykładowego ziemniaka najlepiej obrać za pomocą cięć w powyższy sposób.
1. Czyli takim, którego każdy kąt wewnętrzny jest mniejszy niż
.
Autor zadania: Marcin Pilipczuk.