У вас есть строго выпуклый многоугольник с \(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
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач