Polygon
Contest: Codeforces Round 743 (Div. 1)
Difficulty rating: 3000
Tags: binary search, dp, geometry

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.

Input format:
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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
8 4
-2 -4
2 -2
4 2
1 5
0 5
-4 4
-5 0
-5 -1

Example output:
11

Example input:
6 3
2 -2
2 -1
1 2
0 2
-2 1
-1 0

Example output:
3

Editorial:
We are going to binary search the answer.
Lets say that we want to check whether we can obtain $$$k+1$$$ regions with area of at least $$$w$$$. From now on a correct cut means a cut that will cut off a region with area of a least $$$w$$$.
Lets consider some interval of vertices $$$(i, j)$$$. We will cut it off virtually using a cut from $$$i$$$ to $$$j$$$. We would like to know how many correct regions we can obtain by performing cuts only in this interval. The area next to the virtual cut is considered a leftover. Given two sets of correct cuts in this interval it's always optimal to choose the one with more cuts and if they have the same amount of cuts, the one with the bigger leftover.
This observation leads us to a dynamic programming solution. Let $$$dp_{i, j}$$$ be a pair $$$(r_{i, j}, l_{i, j})$$$ where $$$r_{i, j}$$$ means the biggest amount of regions and $$$l_{i, j}$$$ the biggest leftover we can obtain by performing cuts in the interval $$$(i, j)$$$.
To calculate this $$$dp$$$ we will iterate over all vertices $$$k$$$ such that $$$i < k < j$$$ and consider vertex $$$k$$$ as one of the vertices that are included in the leftover region. This is a simple transition from states $$$dp_{i, k}$$$ and $$$dp_{k, j}$$$. After we calculate our $$$dp$$$ state we can safely cut this interval off if $$$l_{i, j} \ge w$$$.
Iff $$$r_{1, n} \ge k + 1$$$ the answer equals at least $$$w$$$.
This solution runs in $$$O(n^3 \log(10^{16}))$$$.