题目描述
Little Tomy likes to cover his bread with milk. He does this by dipping it so that its bottom side touches the bottom of the cup, as in the picture below:
Since the amount of milk in the cup is limited, only the area between the surface of the milk and the bottom side of the bread is covered. Note that the depth of the milk is always h and remains unchanged with repeated dippings.
Tomy wants to cover this bread with largest possible area of milk in this way, but doesn't want to dip more than k times. Can you help him out? You may assume that the cup is wider than any side of the bread, so it is possible to cover any side completely.
输入
Each test case begins with a line containing three integers n, k, and h ( 3<=n<=20, 0<=k<=8, 0<=h<=10). A piece of bread is guaranteed to be a convex polygon of n vertices. Each of the following n lines contains two integers xi and yi ( 0<=xxi, yi<= 1,000) representing the Cartesian coordinates of the ith vertex. The vertices are numbered in counterclockwise order. The test case n = 0, k = 0, h = 0 terminates the input.
输出
Output (to two decimal places) the area of the largest possible bread region which can be covered with milk using k dips. The result for test case should appear on its own line.
样例输入
4 2 1
1 0
3 0
5 2
0 4
0 0 0
样例输出
7.46
参考代码
暂无
解析
暂无
