← 返回题目列表

Codeforces · 852/H

H. 鲍勃和阶段

中文机器翻译题面 查看原题

BubbleLand 的公民正在庆祝他们的十周年纪念日,因此他们决定组织一个大型音乐节。鲍勃接到一个任务,要邀请N位著名歌手来参加音乐节。他忙着为他们的演出搭建舞台,完全忘记了按时写邀请邮件,不幸的是他只找到了K个可用的歌手。现在舞台比歌手还多,有些舞台空着。如果 BubbleLand 的公民注意到空荡荡的舞台并发现他不负责任,鲍勃不会喜欢的。

因此,他决定恰好选择K个舞台,形成一个凸集,制作大海报作为该凸集的边缘,并在里面举办节日。虽然这些大海报会让市民看不到外面的空舞台,但鲍勃仍然需要确保他们看不到该区域内的任何空舞台。

由于来的人很多,他希望节日面积尽可能大。帮助他计算在尊重条件的情况下他可以获得的最大面积。如果没有这样的区域,则无法组织节日,答案为 0.00。

输入

输入的第一行包含两个整数 N (3 ≤ N ≤ 200) 和 K (3 ≤ K ≤ min(N, 50)),中间用一个空格分隔,分别代表舞台数和歌手数。

接下来的 N 行中的每一行都包含两个整数 Xi 和 Yi (0 ≤ Xi, Yi ≤ 106),表示阶段的坐标。不存在三个或更多共线级。

输出

输出仅包含一行和一个数字,四舍五入到小数点后两位:最大节日面积。执行舍入时,0.5 及以上向上舍入,其他所有值向下舍入。

示例

输入 #1

5 4
0 0
3 0
2 1
4 4
1 5

输出 #1

10.00

注意

示例说明:在所有可能的有 4 个顶点且内部没有其他顶点的凸多边形中,最大的是具有点 (0, 0)、(2, 1)、(4, 4) 和 (1, 5) 的凸多边形。