题目背景

译自 Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,0.5G}$。

题目描述

给定二维平面上的 $N$ 个点。选择 $K$ 个点，最大化这 $K$ 个点的凸包面积。

此外，要求必须选择平面上 $x$ 坐标最小/最大的两个点。保证这两个点所在的与 $y$ 轴平行的直线上没有其他点，且这两个点的 $y$ 坐标为 $0$。

只需要输出最大的面积。

输入格式

第一行，两个正整数 $N,K$。

接下来 $N$ 行，每行两个整数 $x_i,y_i$，描述一个点。

输出格式

输出一行一个实数，表示凸包的最大面积。

输出不应有多余的前导零或后导零。

6 4
0 0
9 0
2 8
6 5
2 -7
8 -7

67.5

5 3
0 0
10 0
5 0
5 5
5 -5

25

8 5
0 0
15 0
2 -2
4 12
10 -14
6 -12
2 -10
13 10

238

提示

• 样例 $1$ 解释：选择 $(0, 0), (2, −7),(2, 8) , (9, 0)$ 即可。
• 样例 $2$ 解释：选择 $(0, 0), (10, 0) , (5, −5)$ 即可。

亦可参阅下图。

数据范围

对于 $100\%$ 的数据，保证：

• $3\le K\le N\le 3\, 000$；
• 给出的点不重合；
• $x$ 坐标最小/最大的点唯一，且对应的点的 $y$ 坐标为 $0$。