#3326. [Baltic2005]polygon

[Baltic2005]polygon

Polygon

题面翻译

题目描述

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

输入格式

第一行输入两个数 nn,kk

之后 nn 行每行两个整数 xix_i,yiy_i,逆时针给出 nn 边形顶点的坐标。

输出格式

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

题目描述

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

You will make k 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 k cuts.

输入格式

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

The following n n lines describe vertices of the polygon in anticlockwise direction. The i i -th line contains two integers xi x_i , yi y_i ( xi,yi108 |x_i|, |y_i| \le 10^8 ) — the coordinates of the i 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 k cuts multiplied by 2 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) (-2, -4) and (4,2) (4, 2) ,
  • (2,4) (-2, -4) and (1,5) (1, 5) ,
  • (5,1) (-5, -1) and (1,5) (1, 5) ,
  • (5,0) (-5, 0) and (0,5) (0, 5) .

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

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

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