#3326. [Baltic2005]polygon
[Baltic2005]polygon
Polygon
题面翻译
题目描述:
给定一个凸 边形,将这个 边形沿顶点连线分割 次,每条分割线不能相交,得到 个小多边形。问分割出的多边形面积最小值最大是多少。
输入格式:
第一行输入两个数 ,。
之后 行每行两个整数 ,,逆时针给出 边形顶点的坐标。
输出格式:
输出一行表示答案的两倍。可以证明这是个整数。
题目描述
You are given a strictly convex polygon with vertices.
You will make 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 cuts.
输入格式
The first line contains two integers , ( , ).
The following lines describe vertices of the polygon in anticlockwise direction. The -th line contains two integers , ( ) — the coordinates of the -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 cuts multiplied by .
样例 #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:
- and ,
- and ,
- and ,
- and .
Points , , , determine the smallest region with double area of . In the second example, it's optimal to make cuts between the following pairs of vertices:
- and ,
- and ,
- and .
Points , , determine one of the smallest regions with double area of .