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)$。 ![](https://espresso.codeforces.com/36529cfbcb7067cbac5d430dc05849b68c961b3d.png) 点 $(-5,-1),(1,5),(0,5),(-5,0)$ 确定双倍面积为 $11$ 的最小区域。 在第二个示例中,在以下几对顶点之间进行切割是最佳选择: - $(2,-1)$ 和 $(0,2)$, - $(2,-1)$ 和 $(1,0)$, - $(-1,0)$ 和 $(0 2)$。 ![](https://espresso.codeforces.com/67ac81c492919c77cb99cdf3018ec635a064068c.png) 点 $(2,-2),(2,-1),(-1,0)$ 决定了一个最小区域的双倍面积为 $3$ 。