308771: CF1572E. Polygon
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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