CF1572E Polygon
题目描述
给定一个凸 $n$ 边形,将这个 $n$ 边形沿顶点连线分割 $k$ 次,每条分割线不能相交,得到 $k+1$ 个小多边形。问分割出的多边形面积最小值最大是多少。
输入格式
第一行包含两个整数 $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$ 个顶点的坐标。
保证这个多边形是凸形,并且没有相邻的两条边是平行的。
输出格式
输出一行表示答案**的两倍**。可以证明这是个整数。
说明/提示
在第一个例子中,最好在以下几对顶点之间进行切割:
- $(-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$ 。