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

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

说明

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 $ .