pb 讲课题，还是有点坑的。
考虑到 \(n\) 和 \(k\) 都很小，可以先将所有点对于 \(x,y\) 坐标排序，枚举答案凸包最左边那个点 \(p\)。然后设 \(f_{i,j}\) 表示走了 \(i\) 步，目前位于 \(j\) 点的最大面积，答案就是 \(f_{k,p}\)。
考虑从 \(f_{i-1,x}\) 转移到 \(f_{i,y}\)，此时 dp 受如下限制影响：
- 此时加入点 \(y\) 后，路径上的点的集合仍然是个凸多边形。
- 加入点 \(y\) 后，路径上的点的集合构成的凸多边形内部不包含任何给定的点。
由于任意的转移前后都满足限制，考虑将凸包拆分成若干个以 \(p\) 为顶点的三角形，每次相当于加入以 \(p,x,y\) 为顶点的三角形，如果我们是逆时针加入点，转换限制如下：
- \(x\to y\) 的直线要比 \(x\) 转移过来的直线往左偏。
- \(p,x,y\) 为顶点的三角形不包含其它点。
第一个限制满足了凸多边形的性质，第二个限制归纳满足了凸包内部没有点的限制。
但是此时又有一个问题：如何确定 \(x\) 转移过来的直线的斜率。一个简单的想法是再加一维状态 \(k\) 表示第 \(i\) 步是由 \(k\) 走到 \(j\)，但是复杂度 \(O(n^4k)\)，寄了。
不妨优化转移，考虑对转移的边进行极角排序，那么后面的边就一定能从前面的边转移过来了。至此，复杂度是 \(O(n^3k)\) 的，足以通过本题。
有一个细节问题，就是 \(p\to x\) 向量如果 \(x\) 坐标为 \(0\) 且 \(y<0\)，那么极角排序时会把它放到开头，此时对于所有点排序时 \(x\) 坐标相同应将 \(y\) 坐标大的放前面，否则转移不到。
// Problem: H. Bob and stages
// Contest: Codeforces - Bubble Cup X - Finals [Online Mirror]
// URL: https://codeforces.com/problemset/problem/852/H
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 250;
const int K = 60;
const int inf = 0x3f3f3f3f3f3f;
struct vec {
int x, y;
vec () { }
vec (int _x, int _y) : x(_x), y(_y) { }
vec operator + (const vec &rhs) const { return vec(x + rhs.x, y + rhs.y); }
vec operator - (const vec &rhs) const { return vec(x - rhs.x, y - rhs.y); }
int operator * (const vec &rhs) const { return x * rhs.y - y * rhs.x; }
} a[N];
int n, k, ans, t[N], f[K][N], vis[N][N];
vector<tuple<vec, int, int> > tr;
int sd(vec s) {
if (s.x >= 0 && s.y < 0) return 1;
else if (s.x >= 0 && s.y >= 0) return 2;
else if (s.x < 0 && s.y >= 0) return 3;
else return 4;
}
bool operator < (const vec &lhs, const vec &rhs) {
if(sd(lhs) != sd(rhs)) return sd(lhs) < sd(rhs);
return lhs * rhs > 0;
}
signed main() {
n = rd(), k = rd();
for (int i = 1; i <= n; i++)
a[i].x = rd(), a[i].y = rd();
sort(a + 1, a + n + 1, [](vec &x, vec &y) {
return x.x == y.x ? x.y > y.y : x.x < y.x;
});
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i ^ j) tr.pb(mt(a[i] - a[j], j, i));
sort(tr.begin(), tr.end());
for (int p = 1; p <= n; p++) {
int ct = 0;
for (int i = p + 1; i <= n; i++) t[++ct] = i;
if (ct <= k - 2) break;
sort(t + 1, t + ct + 1, [&](int &x, int &y) {
return (a[x] - a[p]) < (a[y] - a[p]);
});
for (int i = 1; i <= n; i++)
memset(vis[i], 0, sizeof(int) * (n + 10));
for (int i = 1; i <= ct; i++) {
vis[p][t[i]] = vis[t[i]][p] = 1;
if (i > 1) vis[t[i - 1]][t[i]] = 1;
}
for (int i = 1; i <= ct; i++) {
int l = i + 1;
for (int j = i + 2; j <= ct; j++)
if ((a[t[l]] - a[t[i]]) * (a[t[j]] - a[t[i]]) > 0)
vis[t[i]][t[j]] = 1, l = j;
}
for (int i = 0; i <= k; i++)
for (int j = 1; j <= n; j++) f[i][j] = -inf;
f[0][p] = 0;
for (auto [_, x, y] : tr) {
if (!vis[x][y]) continue;
int s = abs((a[x] - a[p]) * (a[y] - a[p]));
for (int j = 1; j <= k; j++)
f[j][y] = max(f[j][y], f[j - 1][x] + s);
}
ans = max(ans, f[k][p]);
}
printf("%.2lf", ans / 2.);
return 0;
}