多边形

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一个严格凸的 $n$ 边形。你需要作出恰好 $k$ 条分割线，并满足：

• 每条分割线连接两个不同且不相邻的原多边形顶点；
• 任意两条分割线只能在原多边形的顶点处相交。

这些分割线把多边形分成 $k+1$ 个区域。请最大化其中面积最小区域的面积。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示第 $i$ 个顶点的坐标。顶点按逆时针顺序给出。

保证多边形严格凸，且任意两条相邻边不平行。

输出格式

输出一个整数，表示最优方案中最小区域面积的两倍。

样例输入 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

样例解释

样例 1 的一种最优分割如下图所示；最小区域的两倍面积为 $11$。

样例 2 的一种最优分割如下图所示；最小区域的两倍面积为 $3$。

数据范围

对于所有数据：

• $3\le n\le 200$；
• $0\le k\le n-3$；
• $|x_i|,|y_i|\le 10^8$。