Олимпиадный тренинг

Задача . H. Боб и сцены


Жители BubbleLand празднуют свое 10-летие, поэтому они решили организовать большой музыкальный фестиваль. Перед Бобом стояла задача пригласить N известных исполнителей на фестиваль. Однако, он был слишком занят расстановкой сцен, поэтому он забыл разослать письма с приглашениями вовремя, и сейчас он нашел только K свободных исполнителей. Теперь сцен больше, чем исполнителей, поэтому некоторые из сцен останутся пустыми. Боб не хочет, чтобы жители BubbleLand заметили пустые сцены и поняли, что он был безответственным.

Боб решил выбрать ровно K сцен, формирующих выпуклое множество, закрыть ребра этого выпуклого множества большими рекламными щитами и провести фестиваль внутри. Щиты скроют пустые сцены, находящиеся снаружи, от жителей, но кроме этого, Бобу еще надо сделать так, чтобы внутри не осталось ни одной пустой сцены.

Так как придет много людей, он хочет сделать площадь фестиваля максимально возможной. Помогите ему вычислить максимальную площадь, которую он может получить, выполнив все ограничения. Если это вообще невозможно, то ответ равен 0.00.

Входные данные

Первая строка содержит два целых числа N (3 ≤ N ≤ 200) и K (3 ≤ K ≤ min(N, 50)), разделенные пробелами, описывающих число сцен и число исполнителей, соответственно.

Каждая из следующих N строк содержит два целых числа Xi и Yi (0 ≤ Xi, Yi ≤ 106), описывающие координаты очередной сцены. Не существует трех сцен, лежащих на одной прямой.

Выходные данные

Выведите одну строку с одним числом, округленным до ровно двух знаков после запятой: максимально возможную площадь фестиваля. Округление производится таким образом, что 0.5 и более округляется вверх, все остальное округляется вниз.

Примечание

Пояснение к примеру: из всех возможных выпуклых многоугольников с 4 вершинами и без других точек внутри наибольший имеет координаты вершин (0, 0), (2, 1), (4, 4) и (1, 5).


Примеры
Входные данныеВыходные данные
1 5 4
0 0
3 0
2 1
4 4
1 5
10.00

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя