问题：点集 Q 的凸包 (convex hull) 是一个最小的凸多边形 P：Q 中的每个点或在 P 的边界上或 在 P 的内部，我们用 CH(Q) 表示点集 Q 的凸包。 问题定义： 输入：平面上的点集 Q 输出：Q 的凸包 CH(Q)
(a) 请给出一种算法计算 CH(Q), 叙述基本思想并写出伪代码;
(b) 分析算法时间复杂度;
(c) 分析算法的正确性;
（1）Graham扫描法主要用一个栈来解决凸包问题，点集Q中每个点都会进栈一次，不符合条件的点会被弹出，算法终止时，栈中的点就是凸包的顶点(逆时针顺序在边界上)。
1、先选出点集Q（p0,p1,p2,…,pn）中y坐标最小的点记为p0, 如果y坐标相同则相同点中x坐标最小的点。
2、把（p0,p1,p2,…,pn）按照极角从小到大排序(以p0为极点)，极角相同的点按照到的距离从小到大排序。
3、把p0,p1,p2压入栈。
4、遍历剩下的点(p3,p4,p5,…,pn),while循环把发现不是凸包顶点的点移除出去，因为当逆时针遍历凸包时，我们应该在每个顶点向左转。因此当while循环发现在一个顶点处没有向左转时，就把该顶点移除出去。至于如何判断向左向右则是根据叉积来判断。
伪代码如下：
GRAHAM-SCAN(Q)
1 let p0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie
2 let<p1,p2,…,pn> be the remaining points in Q ,sorted by polar angle in counterclockwise order around p0
(if more than one point has the same angle ,remove all but the one is farthest from p0)
3 if m<2
4 return "convex hull is empty"
5 else let S be an empty stack
6 PUSH(p0 , s)
7 PUSH(p1 , s)
8 PUSH(p2 , s)
9 for i = 3 to m
10 while the angle formed by points NEXT-TO-TOP(S),TOP(S)
and pi makes a nonleft turn
11 POP(S)
12 PUSH(pi , S)
13 return S
（2）分析算法的时间复杂度
1. 求Q中y-坐标值最小的点p0 : 时间O(n)
2. 按照与p0极角(逆时针方向) 大小排序Q中其余点，结果为:<p1,p2,…,pn>
时间O(nlogn)
3. Push p0,p1,p2 into S : 时间O(1)
4. FOR i=3 TO n DO
5. While Next-to-top(S)、Top(S) 和pi形成非左移动 Do Pop(S); Push(pi,S) : 需要O(n)时间
6. Return S.
因为每个顶点至多进栈一次，出栈一次，每次需要常数计算时间
综上，T(n) = O(nlogn)
（3）分析算法的正确性
定理:设n个二维点的集合Q是Graham-Scan算法的输入，|Q|³3，算法结束时，栈S中自底到顶存储CH(Q)的顶点（按照逆时针顺序）
证明: 使用循环不变量方法
Loop invariant : 在处理第i个顶点之前, 栈S中自底到顶存储CH(Qi-1)的顶点.
Proof by induction（通过归纳证明）
Initialization: (第6~8步)
处理i=3之前，栈S中包含了Qi-1=Q2={p0 ,p1 ,p2}中的顶点, 这三个点形成了一个CH. 循环不变量为真.
Maintenance:
1.设在处理第i(i³3)个顶点之前, 循环不变量为真，即：栈S中自底到顶存储CH(Qi-1)的顶点. 往证： 算法执行9~12步之后，栈S中自底到顶存储CH(Qi)的顶点.
2.10~11步while循环执行结束后，第12步将pi压入栈之前，设栈顶元素为pj，次栈顶元素为pk，则此时，栈中包含了与for循环的第j轮迭代后相同的顶点，即CH(Qj)，循环不变量为真.
3.执行第7步之后, pi入栈, 则栈S中包含了CH(QjÈ{pi})中的顶点,且这些点仍按逆时针顺序,自底向上出现在栈中.即： CH(QjÈ{pi})= CH(Qi )
4.对于任意一个在第i轮迭代中被弹出的栈顶点pt，设pr为紧靠pt的次栈顶点, pt被弹出当且仅当pr、pt、pi构成非左移动。因此, pt不是CH(Qi )的一个顶点，即CH(Qi-{pt})= CH(Qi )。 设Pi为for循环第i轮迭代中被弹出的所有点的集合,则有CH(Qi-Pi )= CH(Qi ),又 Qi-Pi= QjÈ{pi}，故有CH(QjÈ{pi})= CH(Qi-Pi)=CH(Qi)
5.即得到：一旦将pi压入栈后, 栈S中恰包含CH(Qi)中的顶点, 且按照逆时针顺序，自底向上排列。
Termination:
i=n+1,栈S中自底到顶存储CH(Qn)的顶点, 算法正确.
证毕.
