Polygon

题面翻译

题目描述：

给定一个凸 $n$ 边形，将这个 $n$ 边形沿顶点连线分割 $k$ 次，每条分割线不能相交，得到 $k+1$ 个小多边形。问分割出的多边形面积最小值最大是多少。

输入格式：

第一行输入两个数 $n$,$k$。

之后 $n$ 行每行两个整数 $x_i$,$y_i$，逆时针给出 $n$ 边形顶点的坐标。

输出格式：

输出一行表示答案的两倍。可以证明这是个整数。

题目描述

You are given a strictly convex polygon with $n$ vertices.

You will make $k$ cuts that meet the following conditions:

• each cut is a segment that connects two different nonadjacent vertices;
• two cuts can intersect only at vertices of the polygon.

Your task is to maximize the area of the smallest region that will be formed by the polygon and those $k$ cuts.

输入格式

The first line contains two integers $n$ , $k$ ( $3 \le n \le 200$ , $0 \le k \le n-3$ ).

The following $n$ lines describe vertices of the polygon in anticlockwise direction. The $i$ -th line contains two integers $x_i$ , $y_i$ ( $|x_i|, |y_i| \le 10^8$ ) — the coordinates of the $i$ -th vertex.

It is guaranteed that the polygon is convex and that no two adjacent sides are parallel.

输出格式

Print one integer: the maximum possible area of the smallest region after making $k$ cuts multiplied by $2$ .

样例 #1

样例输入 #1

8 4
-2 -4
2 -2
4 2
1 5
0 5
-4 4
-5 0
-5 -1

样例输出 #1

11

样例 #2

样例输入 #2

6 3
2 -2
2 -1
1 2
0 2
-2 1
-1 0

样例输出 #2

3

提示

In the first example, it's optimal to make cuts between the following pairs of vertices:

• $(-2, -4)$ and $(4, 2)$ ,
• $(-2, -4)$ and $(1, 5)$ ,
• $(-5, -1)$ and $(1, 5)$ ,
• $(-5, 0)$ and $(0, 5)$ .

Points $(-5, -1)$ , $(1, 5)$ , $(0, 5)$ , $(-5, 0)$ determine the smallest region with double area of $11$ . In the second example, it's optimal to make cuts between the following pairs of vertices:

• $(2, -1)$ and $(0, 2)$ ,
• $(2, -1)$ and $(1, 0)$ ,
• $(-1, 0)$ and $(0, 2)$ .

Points $(2, -2)$ , $(2, -1)$ , $(-1, 0)$ determine one of the smallest regions with double area of $3$ .