← 返回题目列表

Codeforces · 1572/E

E. 多边形

中文机器翻译题面 查看原题

给定一个具有 $$$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$$$ 两倍的最小区域之一。