132 - Bumpy Objects

觀察上圖中的三個物體。它們均由多邊形表示,並給定其重心和各頂點的坐標。在上圖中,重心由黑色方塊表示。頂點的編號按逆時針方向依次給出。

將一個物體的輪廓多邊形上某兩個頂點連成一條線段,且該線段未穿越多邊形的內部,然後通過旋轉多邊形使該線段達到水平,若重心在這條線段之上且位於線段兩端點之間,就認為該物體可以擺放平穩。一般情況下,物體有多個可以放穩的位置,每個穩定位置均由對應的線段(稱作“基線”)表示。一條基線會經過至少兩個多邊形上的點(即端點),基線就由這些點中最大的編號表示。

寫一個程序計算出編號最小的基線。對於上圖中的物體,“object 1”要求的基線為 6,“object 2”為6,“square”為 2。你可以假設物體都是規則的,即不存在自相交的輪廓多邊形,但有可能是凹多邊形。

Input and Output

輸入有多行組成,每組數據3行。第一行是不超過20個字符長度的物體標識符,第二行是物體的重心坐標,接下來的一行是物體各頂點坐標,由兩個零(0 0)表示結束,沒有多餘的行。可能會有多組數據集(物體),輸入的數據由#號字符串表示結束。

輸出也有多行組成,每行前面是物體標識符,後面是對應的基線編號。 (譯註:按照UVa OJ的管理員在官方論壇裡的回复,物體標識符和基線編號之間應有1個或多個空格隔開)

Sample input

Object2
4 3
3 2  5 2  6 1  7 1  6 3  4 7  1 1  2 1  0 0
Square
2 2
1 1  3 1  3 3  1 3  0 0
#

Sample output

Object2             6
Square              2