시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 339 59 42 17.004%

문제

선영이는 쓰레기를 편하게 버리기 위해서 빌딩에 쓰레기 슈트를 만들었다. 쓰레기 슈트는 빌딩에 설치할 수 있는 속이 빈 튜브다. 튜브로 쓰레기를 떨어뜨리면, 쓰레기는 지하실까지 떨어지게 된다.

쓰레기 슈트를 만드는 일은 매우 어려운 일이다. 사람들이 무엇을 버릴지 알 수 없기 때문에, 쓰레기 슈트에 들어가지 않는 쓰레기를 버린다면, 슈트가 막혀버릴 수 있기 때문이다. 쓰레기 슈트를 만드는데 드는 비용은 그 크기에 비례한다. 따라서, 최대한 작게 만드는 것이 효율적이다.

먼저, 쓰레기 슈트를 만드는 문제를 2차원으로 단순화 시켜보자. 슈트는 일정한 너비를 가지고 있고, 다각형으로 모델링된 물체를 이 곳의 상단에 넣을 수 있다.

물체를 넣기 전에, 슈트에 들어갈 수 있게 돌려야 할 수도 있다. 슈트에 던진 이후에는 일직선으로 아래로 떨어지고, 그 동안 물체는 회전하지 않는다.

아래 그림은 물체를 쓰레기 슈트에 들어갈 수 있게 회전시킨 다음 버리는 그림이다.

어떤 물체가 주어진다. 이 물체가 통과할 수 있는 가장 작은 슈트의 너비를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 물체(다각형)의 꼭지점의 개수 n이 주어진다. (3 ≤ n ≤ 100)

다음 n개 줄에는 꼭지점의 좌표 xi와 yi가 주어진다. (0 ≤ xi, yi ≤ 104) 꼭지점은 다각형을 이루는 순서대로 주어진다. 

입력으로 주어지는 다각형의 좌표는 모두 서로 다르며, 다각형의 변은 교차하지 않는다. 엄밀히 따지면, 인접한 변은 한 꼭지점을 공유한다는 예외가 하나 있다. 물론, 이 경우는 교차하는 것으로 생각하지 않는다.

마지막 테스트 케이스의 다음 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 케이스 번호와 가장 작은 쓰레기 슈트의 너비를 출력한다. 너비는 가장 가까운 0.01의 배수로 올림하여 소수점 둘째 자리까지 출력한다.

예제 입력

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

힌트

출처

ACM-ICPC > World Finals > 2011 World Finals K번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: tae