У вас есть строго выпуклый многоугольник с \(n\) вершинами.
Вы сделаете \(k\) разрезов, удовлетворяющих следующим условиям:
- каждый разрез — отрезок, соединяющий две различные не соседние вершины;
- два разреза могут пересекаться только в вершинах многоугольника.
Ваша задача — максимизировать площадь минимальной по площади области, образованной многоугольником и этими \(k\) разрезами.
Выходные данные
Выведите одно целое число: максимально возможную площадь самой маленькой области после \(k\) разрезов, умноженную на \(2\).
Примечание
В примере оптимально провести разрезы между следующими парами вершин:
- \((-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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 4
-2 -4
2 -2
4 2
1 5
0 5
-4 4
-5 0
-5 -1
|
11
|
|
2
|
6 3
2 -2
2 -1
1 2
0 2
-2 1
-1 0
|
3
|