Convex Hull Finding

**题目描述** 现在给你一个单连通轮廓，这是凸或非凸(凹)的形状，使用任何算法找到它的凸壳，即最小的凸轮廓包围给定的形状。如果给定的轮廓是凸的，那么它的凸包就是原始轮廓本身。形状的最大尺寸为512x512，形状的最大顶点数为512。现在请优秀的你编写一个程序来实现你的完美无瑕的算法。 **输入格式** 在X-Y笛卡尔平面中，顶点的顺序是逆时针的(如果你考虑显示窗口的原点在左上角，那么顶点的方向是顺时针的)，并且没有一个相邻的顶点是共线性的。由于所有的形状都是封闭的轮廓，所以说，最后一个顶点应该与第一个点相同。在一个给定的文件中有几组数据。负数“-1”用于分隔每一组数据。 | 行号 | 文件中的数据 | 解释 | | -----------: | :----------- | :----------- | | 1 | K | 文件中的数据个数 | | 2 | N | 第一个形状的顶点个数 | | 3 | X₁ , Y₁ | 第一个点的坐标 | | 4 | X₂ , Y₂ | 第二个点的坐标 | | … | | | | N+2 | Xn , Yn | 第N个点的坐标 | | N+3 | -1 | 数据分割标志 | | N+4 | M | 第二个形状的顶点个数 | | N+5 | X₁ , Y₁ | 第一个点的坐标 | | … | | | **注意：** 行号、文件中的数据和说明没有在文件中给出。这里显示它们只是为了帮助您阅读数据。 第一个数据的轮廓形状及其凸包如下图所示  **输出格式** 输出所有输入形状的凸包（就是将凸包的各个顶点输出），**记得输出-1**。另外，Y值最小的顶点应该是第一个点，如果有相同Y值的点，那么在这些点中最小的X值应该是首个点。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=622 [PDF](https://uva.onlinejudge.org/external/6/p681.pdf) 



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