In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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ęć?
Napisz program, który:
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.
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.
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.