description: 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
  
  The first line contains two integers n, k (3 ≤ n ≤ 200, 0 ≤ k ≤ 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| ≤ 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
  
  Print one integer: the maximum possible area of the smallest region after making k cuts multiplied by 2.
  
  Examples
  
  Input
  
  
  8 4
  -2 -4
  2 -2
  4 2
  1 5
  0 5
  -4 4
  -5 0
  -5 -1
  
  
  Output
  
  
  11
  
  
  Input
  
  
  6 3
  2 -2
  2 -1
  1 2
  0 2
  -2 1
  -1 0
  
  
  Output
  
  
  3
  
  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). 
  
  <image> 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). 
  
  <image> Points (2, -2), (2, -1), (-1, 0) determine one of the smallest regions with double area of 3. 
solution: #include <bits/stdc++.h>
  using namespace std;
  int n, m, i, j, rlj, k, nxt, cur, len, res, x[444], y[444], mx[202][202];
  long long le, ri, mid, s[202][202], f[202][202];
  long long cross(long long xa, long long ya, long long xb, long long yb) {
    return abs(xa * yb - ya * xb);
  }
  long long cross(int i, int j, int k) {
    return cross(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]);
  }
  void tryupd(int i, int j, int v, long long s) {
    if (v > mx[i][j] || (v == mx[i][j] && s < f[i][j])) {
      mx[i][j] = v;
      f[i][j] = s;
    }
  }
  int main() {
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
      scanf("%d%d", &x[i], &y[i]);
      x[i + n] = x[i];
      y[i + n] = y[i];
    }
    for (i = 0; i < n; i++)
      for (len = 2; len < n; len++)
        s[i][len] = s[i][len - 1] + cross(i, i + len - 1, i + len);
    le = 0;
    ri = s[0][len - 1];
    while (le < ri) {
      mid = (le + ri) / 2 + 1;
      res = 0;
      for (len = 2; len + 1 < n && res < m; len++)
        for (i = 0; i < n; i++) {
          mx[i][len] = 0;
          f[i][len] = 0;
          j = i + len;
          rlj = j % n;
          if (s[i][len] >= mid && s[rlj][n - len] >= mid) {
            mx[i][len] = 1;
            f[i][len] = s[i][len];
            tryupd(i, len, mx[i][len - 1], f[i][len - 1]);
            nxt = i + 1;
            if (nxt >= n) nxt -= n;
            tryupd(i, len, mx[nxt][len - 1], f[nxt][len - 1]);
            cur = nxt + 1;
            for (k = 2; len - k >= 2; k++, cur++) {
              if (cur >= n) cur -= n;
              tryupd(i, len, mx[i][k] + mx[cur][len - k],
                     f[i][k] + f[cur][len - k]);
            }
            if (s[i][len] - f[i][len] >= mid) {
              ++mx[i][len];
              f[i][len] = s[i][len];
            }
            if (mx[i][len] > res) res = mx[i][len];
          }
        }
      if (res >= m)
        le = mid;
      else
        ri = mid - 1;
    }
    printf("%lld\n", ri);
    return 0;
  }
  