2013年7月11日 星期四

1111 - Trash Removal

Allied Chute Manufacturers 是一家建造垃圾槽的公司,垃圾槽被設置在建築物中,垃圾將會從頂部落下,最後被收集在地下室。垃圾槽的設計相當簡單,根據被丟入垃圾的大小,盡可能地設計近似的大小,因為生產成本與槽的大小成正比,因此公司總是製造最小的大小。但是要找到合適的大小非常困難。

我們垃圾槽設計問題簡化為 2 維空間,一個垃圾槽是一個直落的架構,以及有一個恆定的寬度,當一個物體(垃圾為一個多邊形)被丟入後,再它落入垃圾槽前,可以將它旋轉至一個最佳的大小。一旦落入後,它將不會在移動中旋轉,從下圖可以看出旋轉後可以被丟入垃圾槽。

根據給定的多邊形,寫一個程序計算最小垃圾槽的寬度。

Input 

輸入有多組測資,每組測資第一行有一個整數 n (3 <= n <= 100),表示多邊形的點個數。
接下來會有 n 行,每行會有兩個整數 xi and yi (0 <= xi, yi <= 104),表示多邊行的頂點,
所有的點不會重覆,且多邊形的邊不會重疊。


n = 0 結束程式。

Output 

對於每組測資,輸出第幾筆測資,且輸出一個最小寬度,四捨五入到小數點第二位。
答案誤差在 1/100 內都會是正確的。

Sample Input 

3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0

Sample Output 

Case 1: 2.40
Case 2: 14.15

沒有留言:

張貼留言