1 人解决，2 人已尝试。
1 份提交通过，共有 6 份提交。
9.8 EMB 奖励。
1876. Invention
单点时限: 2.0 sec
内存限制: 256 MB
In the future, farmers won’t have to rely on primitive scarecrows to keep the birds away from their crops. A new revolutionary invention, an “electronic scarecrow”, will make sure the birds stay out of the farmers’ fields forever.
If you have three electronic scarecrows located on a field so that they form a triangle, a bird won’t be able to fly inside this area because it will get zapped by a laser beam coming out from the scarecrows. Of course, if you have more scarecrows, the whole area that is surrounded by these scarecrows becomes protected (this area is known as the convex hull). Consider the picture below:
The black dots represents electronic scarecrows and the area shaded gray is the part of the field that is inaccessible to the birds.
This sounds great, but there are two drawbacks. First, the scarecrows are of course very expensive, so a farmer can’t afford very many of them. Second, they are quite heavy and need firm soil to stand on, and must also be in range of a power outlet. This severely limits the number of locations the farmer can place such scarecrows.
Given the coordinates of possible locations for the scarecrows and the maximum number of scarecrows the farmer can afford to buy, calculate the largest area that can be guarded by these scarecrows. The farmer’s field is a rectangular area, and all locations given will be inside this area.
输入格式
There are many test cases!In each test case,the first line is a interger N(3<=N<=100),then in next N lines,each line contain two integers x(0<=x<=10000),y(0<=y<=10000) the coordinates of possible locations for the scarecrows.The last line is an int n(3<=n<=100), the maximum number of scarecrows the farmer can afford to buy.The data are generated by random!
输出格式
you should output a double containing the largest area the scarecrows can cover. You may safely assume that it will always be possible to put the scarecrows so they will cover an area strictly greater than 0.A solution will be judged correct if the absolute or relative error is within 1e-9.
样例
Input
7 2 2 1 5 6 1 5 5 3 7 7 6 9 4 4 8 183 1000 229 823 723 0 510 412 395 786 936 446 447 312 328 286 15
Output
24.0 347200.0 Hint: case 1:Selecting the points (2,2), (6,1), (9,4) and (3,7) will yield an area of 24 (this corresponds to the picture in the figure above). case 2:The farmer can afford more scarecrows than there are possible locations for him to put them.
创建: 16 年，1 月前.
修改: 6 年，8 月前.
最后提交: 12 年，11 月前.
来源: N/A
题目标签