Q681: Convex Hull Finding

一個圖形的輪廓（contour），形狀可能是凸的或不是凸的（有凹的地方）。請運用任何一種可行的演算法，找出輪廓的凸包（convex hull）、也就是剛好能包住其形狀的凸輪廓。如果輪廓形狀是凸的，那麼它的凸包便是輪廓本身。這裡設定圖形的尺寸最大為 512 × 512，最多有 512 個頂點。請寫出一支程式，讀取輸入資料（圖形），執行你的凸包演算法，然後將結果輸出。

Input

圖形的頂點都在二維座標平面上，依逆時針方向排序（如果你想將原點設在視窗的左上角，則會變成順時針方向），而且相鄰的頂點們都不會有三點共線的情 形。由於所有的圖形都是封閉的輪廓，因此圖形的最後一個頂點也會是第一個頂點。測試資料有好幾組，每組測試資料之間皆以 -1 隔開。

行數 輸入資料 釋義
1 K 一個正整數，表示共有多少組測試資料。一組測試資料代表一個圖形。
2 N 一個正整數，表示該圖形有多少個頂點。接下來有N個頂點的座標。
3 X1 Y1 兩個正整數，表示第一個頂點的座標。
4 X2 Y2 兩個正整數，表示下一個相鄰頂點的座標。
... 　 　
N+2 XN YN 兩個正整數，表示最後一個頂點的座標。它會與第一個頂點的座標相同。
N+3 -1 第一組測試資料結束。
N+4 M 一個正整數，表示第二個圖形有多少個頂點。
N+5 XX1 YY1 兩個正整數，表示第一個頂點的座標。
... 　 　

注意：請注意到行數、輸入資料、釋義的欄位內容不會出現在測試資料當中。這裡只是方便讓各位了解測試資料的意義。 

Output

按順序輸出 K 個圖形的凸包。輸出格式應該要與上面表格所述的輸入格式相同。還有，請選出 Y 座標最小的頂點，作為第一個頂點；如果遇到 Y 座標一樣小的情況，再從中選出 X 座標最小的頂點，作為第一個頂點。

Sample Input Sample Output 
3
15
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
30 30
-1
12
50 60
60 20
70 45
100 70
125 90
200 113
250 140
180 170
105 140
79 140
60 85
50 60
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
 
3
8
60 20
250 50
300 200
130 240
76 150
47 76
30 30
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
Translated by DJWS