Informatica Online Judge

  쓰레기 제거 [2300 / 08FC]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 7   Total Tried : 10


The Champion of this Problem (C++) : gs18084 - ms / 780byte
My Best Submission (C++) : N/A

[ACM ICPC 2011 WF]

Background

연합 이송장치 제조회사는 쓰레기 이동장치를 만드는 회사이다. 쓰레기 이송장치는 속이 빈 관으로 만들어지는데, 건물 내부의 윗층에서 던져 넣은 쓰레기는 그 이송장치를 통해 지하로 이동된다.

쓰레기 이송장치를 설계하는 것은 매우 쉽다. 사람들이 그 안으로 던져 넣을 쓰레기들의 종류에 따라 이동장치에 사용되는 적당한 크기의 관으로 설계하면 되기 때문이다. 이송장치를 만드는데 필요한 비용은 관의 크기에 비례하기 때문에 회사에서는 최대한 작은 크기의 관을 사용해 장치를 만들기를 원한다. 하지만, 적당한 크기의 관을 선택하는 것은 어려운 문제이다.

2차원으로만 생각해 문제를 해결해보자. 관은 위에서 아래로 수직방향으로 설치되고, 쓰레기는 2차원 다각형이라고 하자. 쓰레기가 관으로 던져지기 전에 이리 저리 방향을 돌려 최소 폭으로 회전시킨다. 관으로 던져진 쓰레기는 내려가는 도중에 회전하지 않는다. 아래 그림은 쓰레기가 회전되어 관으로 던져지는 상황을 보여준다.



2차원 다각형 쓰레기들이 주어질 때, 쓰레기를 아래로 통과시킬 수 있는 관의 최소 크기를 계산해보자.

Input

여러 개의 쓰레기 다각형이 순서대로 입력된다.

각 쓰레기 다각형의 첫 번째 줄에는 모서리 개수($n$)가 입력된다. 그 다음 $n$개의 줄에 걸쳐 각 점의 좌표($x_i$, $y_i$)가 순서대로 입력된다. 다각형 모서리의 좌표는 서로 다르고, 다각형을 이루는 직선들은 모서리를 제외하고는 서로 교차하지 않는다.

쓰레기가 더 이상 없는 경우에는 다각형 모서리 개수 대신 0이 입력된다.

[입력값의 정의역]

$3 <= n <= 100$
$0 <= x_i, y_i <= 10^4$

Output

케이스별로 케이스 번호를 출력하고, 각 쓰레기를 통과시킬 수 있는 최소 폭을 소수점 아래 세 번째 자리에서 올림해서, 소수점 아래 둘째자리까지 출력한다. 1/100 이내의 오차는 정답으로 처리된다.

IO Example

입력예시
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0

출력예시
Case 1: 2.40
Case 2: 14.15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]