E D R , A S I H C RSS

Nice Milk

원문보기
----
인기도:C(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:4(1~4)

About NiceMilk

꼬마 토미는 빵에 우유를 찍어 먹는 것을 좋아한다. 빵에 우유를 찍을 때는 빵의 한 변이 컵 바닥에 닿을때까지 빵을 컵 속에 집어넣는다. 그래서 밑에 있는 그림과 같은 모양으로 빵을 우유에 적실 수 있다.
http://online-judge.uva.es/p/v101/p10117.gif
컵에 들어있는 우유의 양이 제한되어 있기 때문에 빵의 밑변과 우유가 이루는 수면 사이 영역만 우유로 적실 수 있다. 우유의 깊이는 h며, 빵에 우유를 계속 찍어도 우유의 높이는 줄지 않는다. 토미는 이런 식으로 최대한 넓은 영역을 우유로 적시려고 한다. 하지만 빵을 우유에 담그는 횟수는 최대 k번으로 제한되어 있다. 컵은 빵을 집어넣을 때 전혀 걸리지 않을 만큼 충분히 크다고 가정하자.

Input

각 테스트 케이스는 세 정수 n, k, h (3≤n≤20, 0≤k≤8, 0≤h≤10)가 들어있는 행으로 시작된다. 빵은 볼록 n각형이다. 그 밑으로 n개의 줄에 걸쳐서 i 번째 꼭지점의 데카르트 좌표를 나타내는 x<sub>i</sub>와 y<sub>i</sub>(0 ≤ x<sub>i</sub>, y<sub>i</sub> ≤ 1,000)라는 두 정수가 입력된다. 꼭지점은 반시계방향 순서로 입력된다. n, k, h가 모두 0으로 입력되면 입력이 종료된다.

Output

k번 담가서 빵을 우유에 적실 수 있는 최대 넓이를 소수점 밑으로 둘째 자리까지 출력한다. 각 테스트 케이스마다 한 줄씩 결과를 출력한다.

Sample Input

{{| 4 2 1
1 0
3 0
5 2
0 4
0 0 0 |}}

Sample Output

{{| 7.46 |}}

풀이

작성자 사용언어 개발시간 코드
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.2928 sec