Александр решил построить себе бассейн около дома и попросил дизайнеров подготовить его проект.
Дизайнеры предложили бассейн в форме выпуклого многоугольника с вершинами в точках $$$P_1, P_2, \ldots, P_n$$$. Вершина $$$P_i$$$ имеет координаты $$$(x_i, y_i)$$$. Вершины перечислены в порядке обхода против часовой стрелки; никакие три вершины не лежат на одной прямой. Известно, что $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$, все $$$y_i \le 0$$$ и $$$y_1 = y_n = 0$$$.
Оценив стоимость работ, Александр решил упростить проект: новый бассейн должен иметь форму выпуклого многоугольника ровно с $$$k$$$ вершинами. Однако рабочие уже перенесли разметку на участок и даже начали копать, поэтому расположение бассейна нельзя выбрать произвольно. Бассейн должен иметь форму выпуклого многоугольника и целиком содержать многоугольник, в котором бассейн планировалось разместить исходно. Каждая сторона бассейна должна лежать на одной из прямых, содержащих стороны исходного многоугольника. Для разных сторон нового бассейна необходимо использовать разные прямые. Кроме того, строительство стенки вдоль стороны $$$P_1P_2$$$ уже началось, поэтому одна из сторон нового бассейна обязательно должна лежать на прямой, проходящей через вершины $$$P_1$$$ и $$$P_2$$$.
При этом участок Александра не слишком большой, поэтому он хочет построить бассейн минимальной площади, удовлетворяющий этим условиям.
На рисунках ниже показаны оптимальные варианты нового бассейна для двух примеров из условия. Заштрихованная область обозначает новый бассейн, а пунктирные линии — продолжения сторон исходного многоугольника.
Помогите ему найти минимально возможную площадь нового бассейна, удовлетворяющего всем требованиям.
В первой строке даны два целых числа $$$n$$$ и $$$k$$$ — количество вершин исходного многоугольника и необходимое количество вершин нового бассейна ($$$3 \le k \le n \le 10^5$$$).
В каждой из следующих $$$n$$$ строк даны два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты вершины $$$P_i$$$ ($$$-10^9 \le x_i \le 10^9$$$, $$$-10^9 \le y_i \le 0$$$).
Гарантируется, что точки являются вершинами выпуклого многоугольника и перечислены в порядке обхода против часовой стрелки. Никакие три вершины многоугольника не лежат на одной прямой. Также гарантируется, что $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$ и $$$y_1 = y_n = 0$$$.
Выведите одно число — минимальную возможную площадь нового бассейна, удовлетворяющего всем требованиям.
Ответ считается правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$.
4 3 0 0 1 -1 2 -1 3 0
2.25
4 4 0 0 1 -1 2 -1 3 0
2
В первом примере новый бассейн должен иметь ровно три стороны. Оптимальным решением является треугольник $$$AED$$$. Его стороны лежат на прямых, содержащих стороны $$$AB$$$, $$$CD$$$ и $$$AD$$$ исходного многоугольника. Площадь этого треугольника равна $$$2.25$$$. Полученный бассейн изображён на рисунке слева.
Во втором примере новый бассейн должен иметь ровно четыре стороны, поэтому можно оставить исходный многоугольник без изменений. Его площадь равна $$$2$$$. Полученный бассейн изображён на рисунке справа.
| Название |
|---|


