218 - Moth Eradication

本題請你找出「凸包」的點集合，並依序列出，請參考下圖：

Input

輸入會有多組測試資料，每組資料的第一列有一個整數 n 表示所有點的個數，接下每一列會給定各點的(x, y)座標，不會有重複的點在相同位置。當 n = 0 表示測試資料結束。

Output

每組測試資料請輸出三列，分別為：

• 第一列：測試資料編號(Region #1, Region #2...)。
• 第二列：請以順時間方向依序輸出所有點，以任何一點開始皆可，注意輸出的第一點與最後一點必須一樣。每點的格式為(x,y)，請輸出到小數點後一位。每個點之間需以 - 隔開。
  
• 第三列：請依範列資料格式輸出該路徑的長度，請輸出到小數點後兩位。
  

Sample Input

3
1 2
4 10
5 12.3
6
0 0
1 1
3.1 1.3
3 4.5
6 2.1
2 -3.2
7
1 0.5
5 0
4 1.5
3 -0.2
2.5 -1.5
0 0
2 2
0

Sample Output

Region #1:
(1.0,2.0)-(4.0,10.0)-(5.0,12.3)-(1.0,2.0)
Perimeter length = 22.10

Region #2:
(0.0,0.0)-(3.0,4.5)-(6.0,2.1)-(2.0,-3.2)-(0.0,0.0)
Perimeter length = 19.66

Region #3:
(0.0,0.0)-(2.0,2.0)-(4.0,1.5)-(5.0,0.0)-(2.5,-1.5)-(0.0,0.0)
Perimeter length = 12.52

原文出處