首先介绍下什么是凸包问题？如下图：
在一个二维坐标系，有若干点杂乱排列着，将最外层的点连接起来构成的凸多边型，它能包含给定的所有的点，这个多边形就是凸包。
寻找凸包的算法有很多种，Graham Scan算法是一种十分简单高效的二维凸包算法，能够在O(nlogn)的时间内找到凸包。
在讲解之前，读者需要了解向量叉积正负的几何意义，如不了解，可以参考http://blog.csdn.net/laojiu_/article/details/52078675
Graham Scan算法的做法是先定下一个起点，一般是最左边的点和最右边的点，然后一个个点扫过去，如果新加入的点和之前已经找到的点所构成的“壳”凸性没有变化，就继续扫，否则就把已经找到的最后一个点删去，再比较凸性，直到凸性不发生变化。分别扫描上下两个“壳”，合并在一起，凸包就找到了。这么说很抽象，我们看图来解释：
我们找下“壳”，上下其实是一样的。首先加入两个点A和C：
然后插入第三个点G，并计算AC×CG的叉积，却发现叉积小于0，也就是说逆时针方向上∠ACG大于180度，于是删去C点，加入G点：
然后就是依照这个步骤便能加入D点。在AD上方是以D为起点。就能够找到AGD和DFEA两个凸壳。合并就得到了凸包。
关于扫描的顺序，有坐标序和极角序两种。坐标序是比较两个点的x坐标，如果小的先被扫描（扫描上凸壳的时候反过来）；如果两个点x坐标相同，那么就比较y坐标，小的先被扫描（扫描上凸壳的时候也是反过来）。极角序使用arctan2函数的返回值进行比较，这个读者自己写吧。
下面贴下代码：
[cpp] view plain copy print ? #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cmath> #include<algorithm> using namespace std; struct Point { double x, y; Point operator-(Point & p) { Point t; t.x = x - p.x; t.y = y - p.y; return t; } double det(Point p)//向量叉积 { return x*p.y - p.x*y; } double dist(Point & p)//两点距离公式 { return sqrt((x - p.x)*(x - p.x) + (y - p.y)*(y - p.y)); } }; bool cmp(Point & p1, Point & p2) { if (p1.x != p2.x) return p1.x < p2.x; return p1.y < p2.y; } Point point[1005]; int convex[1005]; int N;//坐标系的无序点的个数 int getConvexHull() { sort(point, point + N, cmp); int temp; int total = 0; for (int i = 0; i < N; i++)//下凸包 { while (total > 1 && (point[convex[total - 1]] - point[convex[total - 2]]).det(point[i] - point[convex[total - 1]]) <= 0) total--; convex[total++] = i; } temp = total; for (int i = N - 2; i >= 0; i--)//上凸包 { while (total > temp && (point[convex[total - 1]] - point[convex[total - 2]]).det(point[i] - point[convex[total - 1]]) <= 0) total--; convex[total++] = i; } return total;//返回组成凸包的点的个数，实际上多了一个，就是起点，所以组成凸包的点个数是total-1 } int main() { return 0; }
