给定一个具有 $$$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$$$。
示例
输入 #1
8 4 -2 -4 2 -2 4 2 1 5 0 5 -4 4 -5 0 -5 -1
输出 #1
11
输入 #2
6 3 2 -2 2 -1 1 2 0 2 -2 1 -1 0
输出 #2
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$$$ 两倍的最小区域之一。