题目描述

小Tomy喜欢用牛奶泡他的面包。他通过将面包放入杯子中，使其一条边（称为底边）接触杯底，如下图所示：

由于杯子里的牛奶有限，只有部分面包会被牛奶覆盖（如图所示）。具体来说，只有牛奶表面和面包底边之间的区域会被覆盖。注意，这两条线之间的距离始终为$h$——牛奶的深度，这也是已知的。

Tomy希望在不超过$k$次操作的情况下，用这种方式尽可能多地覆盖面包的面积。你能帮助他吗？

（假设杯子的宽度足够大，比面包的任何一边都宽，因此可以完全覆盖任意一边。）

输入格式

输入包含不超过10组测试数据。每组测试数据的第一行包含三个整数$n$、$k$和$h$（$3 \leq n \leq 20$，$0 \leq k \leq 8$，$0 \leq h \leq 10$）。面包保证是一个由$n$个顶点组成的凸多边形。接下来的$n$行，每行包含两个整数$x_i$和$y_i$（$0 \leq x_i, y_i \leq 1000$），表示第$i$个顶点的笛卡尔坐标。顶点按逆时针顺序编号。当输入的测试数据为$n=0$、$k=0$、$h=0$时，输入终止，此时无需处理该测试用例。

输出格式

对于每个测试用例，输出用牛奶覆盖的面包的最大可能面积，保留两位小数。每个测试用例的输出占一行。

样例输入 1

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

样例输出 1

7.46

来源

OIBH Online Programming Contest (OOPC) #1