寻找最大凸多边形

某公司今年的技能鉴定考试是这样的：

给出一系列平面直角坐标系中的点的坐标，写一个程序，找出能够围住这些点的最大的凸多边形，按照顺时针的顺序，将这个最大凸多边形的顶点依次打印出来。如果某个点落在多边形的边上，该点不得打印。

想象一下在每一个点上定一个钉子，然后用一根线把这些钉子给全部围住，线绷直了之后，就是我们要找的凸多边形了。做出这道题的关键是找到算法，同时还必须有一些平面几何的知识。下面给出两个算法。

第一个算法描述如下：

1. 在所有点中，找出纵坐标最大的那个点（最高的点）；如果有好几个点的纵坐标都是最大的，那么就从中选出最左边（横坐标最小）的那个点；可以从数学上严格证明，这个点一定是最大凸多边形的顶点；这里就不证明了，欢迎热血青年来补充。
2. 记录下这个点，记做A，从A出发按如下算法寻找下一个顶点B；
3. 连接A点和剩下的其它点，形成一系列的向量AB，从正向X轴出发顺时针旋转一个角度之后会和向量AB重合，记录下这个夹角为α。
4. 形成最小夹角α的那个点B，就是我们要寻找的下一个顶点B。如果有好几个点都形成相等的最小夹角，那么我们选择线段AB长度最长的那个B点。其它长度较短的点则要从原始点集合中删除掉。
5. 按照同样的算法，从B点出发寻找下一顶点C，使得BC向量和正向X轴的夹角最小β，但是β必须大于上一步的α。
6. 以此类推，从C出发寻找D……，直到找到下一个顶点和A点重合，那么寻找结束。

这个算法，实际上就是模拟拿一根棍子贴着多边形滚动了一周。它要求我们会计算两个点的距离，会计算两个向量的夹角。对于我大五百强的员工而言，这些应该都是小儿科了。

上面的这个算法虽然巧妙，但是却缺少了一些数学上和程序上的美感，显得简单而且粗暴。算法，也要讲究“性感”，下面是一个性感的解法：

从N个点里面找最大凸多边形，比较困难；但是如果我们已经知道了这里面的N-1个点形成的最大凸多边形的顶点，那么再加上第N个点A，根据A和原来凸多边形的位置关系，就可以进一步计算出这N个点形成的新凸多边形顶点了。

没错，我们用到递归，来将复杂问题简单化。递归到最简单的情况，就是三个点，这三个点要么是在一条直线上，要么一定形成一个最简单的凸多边形，那就是三角形。三个点能否形成三角形，是很好判断的J。

以图一为例：已有凸多边形 ABCDEFGHI，现在加入一个新的点 J，显然，加上J之后，最大凸多边形应该变成 ABJEFGHI，CD两顶点要删除，并且用顶点J替换掉C和D；

图一

以图二为例：E点在AB的延长线上，多边形ABCD加上E点后，新的凸多边形应该是AECD，原来的B点应该被E替换掉；但如果ABCD 加上 F 点之后，新的凸多边形应该是ABFCD，原来的凸多边形上没有点要被删除，但是要插入新的F点。如果F点在多边形内部，那么直接抛弃F点即可。多边形还是不变。

图二

问题演变为，如何判断一个孤立点和一个凸多边形的关系呢？知道它们的关系后，怎么来计算出新的凸多边形呢？这里要用到向量的叉乘的概念，两个向量a=(x1,y2)和b=(x2,y2)的叉乘结果：

|a| ^ |b| = |a| * |b| *sin<a,b> = x1*y2 - x2*y1 <a,b>夹角必须小于180°
a ^ b = - b ^ a

叉乘结果是矢量，有正负表示其方向。结果为正，表示叉乘结果指向屏幕外；结果为负，表示叉乘结果指向屏幕里，可以使用右手定则来判定结果方向:右手四指环绕方向从a向b，大拇指方向则是其结果的方向，如果a和b平行，那么其结果为0；

回到图二，多边形ABCD和点E，将多边形顶点按顺时针顺序排列好，从E点出发分别和各顶点连接成向量EA, EB, EC ,ED，放入一个数组，然后依次计算两个相邻向量的叉乘，最后的ED去和EA叉乘，结果如下：[EA ^ EB , EB ^ EC, EC ^ ED ,ED ^EA], 可以发现，每一个元素的正负符号依次是[0 , + , - , -]。0表示E和AB在同一条线上，正数表示E点在BC直线的另一侧（相对于多边形在BC那侧而言），负数则表示在同一侧。

可以判断，叉乘结果的数组中：

1. 如果元素全部是负数，那么这个单点肯定在已知多边形的内部；这个单点应该直接抛弃；
2. 如果只有一个零，其它都是负数，那么这个单点一定在对应的边上；这个单点也应该直接抛弃；
3. 如果有两个零，那这个点一定和原来的某个顶点重合；应该抛弃这个单点；
4. 如果有一个或者多个连续的正数或者0，那么这个单点一定在这几条连续边的外面，例如上面的EA ^ EB , EB ^EC是0 和 正数，那么对应的连续顶点A-B-C，应该保留起始点A和结束点C，中间的点B则应该删除，然后将单点E插入到A和C中间；从而形成新的凸多边形顶点列表AECD；
5. 如果只有一个单独的正数叉乘结果，那就不需要删除任何原来的顶点，而仅需要将新的单点插入即可。
6. 不可能出现多段分开的正数或零序列，比如[-1, -1, 0, 1, 1, 1, 0, -1] 是可能的，但是如下的[-1, -1, 0, 1, -1, 0, 1, -1]叉乘结果序列是绝不可能出现的。 

知道这个关键点之后，剩下的就好办了，下面来看看代码吧，用Ruby写成。分别实现了上面提到的两个算法，最后有用例：

童鞋们，你们考试用的什么算法呢？