Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

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

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

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

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

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

Первая строка содержит два целых числа n, k (3n200, 0kn3).

Следующие n строк описывают вершины многоугольника в порядке против часовой стрелки. i-из этих строк содержит два целых числа xi, yi (|xi|,|yi|108) — координаты 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.