Ziemniak [B]

Limit pamięci: 32 MB

Marcin obiera ziemniaka. Dla uproszczenia przyjmujemy, że ziemniak jest wielokątem wypukłym¹, 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.

Autor zadania: Marcin Pilipczuk.