蛮力法求解凸包问题

1. 问题描述：

问题: 对于平面上n个点，找包围它们的最小凸多边形；

2. 思路：

蛮力算法: 对于每对点 p1和p2 ，判断是否所有其他点都在连接 p1和p2 的直线的同一侧；
思路：两点确定一条直线，如果剩余的其它点都在这条直线的同一侧，则这两个点是凸包上的点，否则就不是。步骤如下：
（1）将点集里面的所有点两两配对，组成 n(n-1)/2 条直线。
（2）对于每条直线，再检查剩余的 (n-2) 个点是否在直线的同一侧。
那么现在出现了一个问题，我们怎样判定一个点在直线的哪一侧呢？方法有两种：
（1）（坐标：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)）行列式求面积 (也就是我们常说的"叉积")

当上式结果为正时，p3在直线 p1p2 的左侧；当结果为负时，p3在直线 p1p2 的右边
（2）将两点构造成直线，将第三点坐标代入，≥0则表示在上方，≤0则表示在下方。

// 算法：蛮力法求解凸包问题
BruteForceConvexHull (P)
// 输入：一个n个(n≥2)的点的列表P,Pi=(Xi,Yi)
// 输出：能够组成凸包的点的列表Qi=(Xi,Yi)
for i  1 to n - 1 do
     for j  i + 1 to n do
          sign1  0; sign2  0;
          a = Yj - Yi; b = Xi - Xj; c = Xi * Yi - Yi * Xj;
          for k  1 to n do
               if k = i || k = j    continue;
               if a * Xk + b * Yk - c ≥ 0    sign1++;
               if a * Xk + b * Yk - c ≤ 0    sign2++;
          if sign2 = 2 - n || sign1 = n - 2
               record the pole
retutn OK