E. Многоугольник
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть строго выпуклый многоугольник с $$$n$$$ вершинами.

Вы сделаете $$$k$$$ разрезов, удовлетворяющих следующим условиям:

  • каждый разрез — отрезок, соединяющий две различные не соседние вершины;
  • два разреза могут пересекаться только в вершинах многоугольника.

Ваша задача — максимизировать площадь минимальной по площади области, образованной многоугольником и этими $$$k$$$ разрезами.

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

Первая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$3 \le n \le 200$$$, $$$0 \le k \le n-3$$$).

Следующие $$$n$$$ строк описывают вершины многоугольника в порядке против часовой стрелки. $$$i$$$-из этих строк содержит два целых числа $$$x_i$$$, $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^8$$$) — координаты $$$i$$$-й вершины.

Гарантируется, что многоугольник выпуклый и никакие две смежные стороны не параллельны.

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

Выведите одно целое число: максимально возможную площадь самой маленькой области после $$$k$$$ разрезов, умноженную на $$$2$$$.

Примеры
Входные данные
8 4
-2 -4
2 -2
4 2
1 5
0 5
-4 4
-5 0
-5 -1
Выходные данные
11
Входные данные
6 3
2 -2
2 -1
1 2
0 2
-2 1
-1 0
Выходные данные
3
Примечание

В примере оптимально провести разрезы между следующими парами вершин:

  • $$$(-2, -4)$$$ и $$$(4, 2)$$$,
  • $$$(-2, -4)$$$ и $$$(1, 5)$$$,
  • $$$(-5, -1)$$$ и $$$(1, 5)$$$,
  • $$$(-5, 0)$$$ и $$$(0, 5)$$$.
Область с наименьшей площадью — четырехугольник с вершинами в $$$(-5, -1)$$$, $$$(1, 5)$$$, $$$(0, 5)$$$, $$$(-5, 0)$$$, удвоенная площадь которого равна $$$11$$$.

Во втором примере оптимально провести разрезы между следующими парами вершин:

  • $$$(2, -1)$$$ и $$$(0, 2)$$$,
  • $$$(2, -1)$$$ и $$$(1, 0)$$$,
  • $$$(-1, 0)$$$ и $$$(0, 2)$$$.
Область с наименьшей площадью — треугольник с вершинами в $$$(2, -2)$$$, $$$(2, -1)$$$, $$$(-1, 0)$$$, удвоенная площадь которого равна $$$3$$$.