K. 쓰레기 처리

Allied Chute Manufacturers는 쓰레기 슈트를 만드는 회사이다. 쓰레기 슈트는 건물에 설치되는 속이 빈 관으로, 꼭대기에서 넣은 쓰레기가 아래로 떨어져 지하에서 수거된다. 쓰레기 슈트 설계는 사실 매우 까다롭다. 사람들이 어떤 종류의 쓰레기를 넣을 것으로 예상되는지에 따라 슈트의 크기가 적절해야 한다. 그리고 슈트 제조 비용은 크기에 비례하므로, 회사는 언제나 가능한 한 작은 슈트를 만들고 싶어 한다. 하지만 올바른 크기를 고르는 것은 어려울 수 있다. 슈트 설계 문제의 2차원(\(2-di\)mensional) 단순화 버전을 생각하자. 쓰레기 슈트는 수직 아래를 향하며 폭이 일정하다. 슈트에 넣을 물체는 다각형으로 모델링한다. 물체를 슈트에 넣기 전에 최적으로 들어가도록 회전시킬 수 있다. 일단 넣으면 물체는 회전하지 않고 곧게 아래로 떨어진다. 다음 그림은 물체가 먼저 회전되어 슈트에 들어맞게 되는 모습을 보여 준다. 주어진 다각형이 통과할 수 있는 슈트의 최소 폭을 계산하는 것이 당신의 임무이다.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 쓰레기를 모델링하는 다각형의 점 개수를 나타내는 정수 \(n\) (\(3 \le n \le 100\))이 있는 줄로 시작한다. 다음 \(n\)개의 줄에는 다각형 꼭짓점의 좌표를 순서대로 나타내는 정수 쌍 \(xi\), \(yi\) (\(0 \le xi\), y\(i \le 10^{4}\))가 주어진다. 한 테스트 케이스의 모든 점은 서로 다름이 보장되며, 다각형의 변은 결코 교차하지 않는다. (엄밀히는 이웃한 두 변이 공통 꼭짓점을 공유하는 불가피한 예외가 하나 있다. 물론 이는 교차로 간주하지 않는다.) 마지막 테스트 케이스 다음에는 0 하나가 있는 줄이 주어진다.

각 테스트 케이스마다 케이스 번호와 함께, 그 물체를 떨어뜨릴 수 있는 가장 작은 슈트의 폭을 출력한다. 최소 폭은 소수점 아래 정확히 두 자리로, \(1/100\)의 배수로 올림(\(up\))하여 출력한다. 올바르게 반올림된 답과의 차이가 \(1/100\) 이내인 답이 정답으로 인정된다. 샘플 출력의 형식을 따른다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011