CF852H Bob and stages

题目描述

泡泡国的市民正在庆祝他们的第十个周年纪念日,因此他们决定举办一场大型音乐节。Bob 的任务是邀请 $N$ 位著名歌手来表演。然而,他一直忙于为表演搭建舞台,结果错过了发邀请邮件的最佳时间,不幸的是他只联系到了 $K$ 位歌手。因此,现在舞台数量多于歌手数量,导致一些舞台会空着。Bob 不想让市民们看到空舞台,从而发现他工作不负责。 因此,他决定选择恰好 $K$ 个舞台,使得这 $K$ 个舞台组成一个凸包,并用巨大的海报将凸包的边围起来,在其内部举办音乐节。通过这些海报,市民无法看到外部的空舞台,但 Bob 还需要确保在该区域内部也看不到任何空舞台。 由于会有很多人参与,Bob 希望音乐节的活动区尽可能大。请你帮助他计算在满足所有条件的情况下,所能获得的最大活动区面积是多少。如果不存在这样的区域,则不能举办音乐节,答案为 $0.00$。

输入格式

输入的第一行包含两个整数 $N\ (3 \leq N \leq 200)$ 和 $K\ (3 \leq K \leq \min(N, 50))$,用一个空格隔开,分别表示舞台的数量和歌手的数量。 接下来的 $N$ 行,每行包含两个整数 $X_{i}$ 和 $Y_{i}$,$0 \leq X_{i}, Y_{i} \leq 10^{6}$,表示每个舞台的坐标。没有三点及以上共线的舞台。

输出格式

输出仅包含一行,一个数字,代表最大活动区的面积,保留并四舍五入到小数点后两位。例如 $0.5$ 及以上进一,其余舍去。

说明/提示

样例说明:在所有满足条件、无其他点在内部的 $4$ 个顶点组成的凸多边形中,最大的面积是由点 $(0,0)$、$(2,1)$、$(4,4)$ 和 $(1,5)$ 组成的多边形。 由 ChatGPT 5 翻译