凸包
(只针对二维平面内的凸包)
一、定义
简单的说,在一个二维平面内有n个点的集合S，现在要你选择一个点集C，C中的点构成一个凸多边形G，使得S集合的所有点要么在G内，要么在G上，并且保证这个凸多边形的面积最小，我们要求的就是这个C集合。
二、算法
求凸包的算法很多，常用的有两种：
1. Graham扫描法，运行时间为O(nlgn)。
2. Jarvis步进法，运行时间为O(nh),h为凸包中的顶点数。
这里主要讨论第一种算法:Graham扫描法
Graham扫描法：
基本思想：使用一个栈来对所有点逐一判断，把不符合条件的点筛出去。
操作：输入集合Q中的每一个点都被压入栈一次，非CH（Q）(表示Q的凸包)中的顶点的点最终将被弹出堆栈，当算法终止时，堆栈S中仅包含CH(Q)中的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。
首先，找一个凸包上的点，把这个点放到第一个点的位置P0。然后把P1~Pm 按照P0Pi的方向排序，可以用矢量积(叉积)判定。
判定过程：
做好了预处理后开始对堆栈中的点<p3,p4,…,pm>中的每一个点进行迭代，在第7到8行的while循环把发现不是凸包中的顶点的点从堆栈中移去。（原理：沿逆时针方向通过凸包时，在每个顶点处应该向左转。因此，while循环每次发现在一个顶点处没有向左转时，就把该顶点从堆栈中弹出。）当算法向点pi推进、在已经弹出所有非左转的顶点后，就把pi压入堆栈中。
整个算法过程如图所示：
<!–
.syntaxhighlighter .toolbar{display:none!important}.syntaxhighlighter table td.code .container{padding-top:1px!important;padding-bottom:1px!important}.syntaxhighlighter table td.gutter .line,.syntaxhighlighter table td.code .line{background-color:#fff!important}.syntaxhighlighter a,.syntaxhighlighter div,.syntaxhighlighter code,.syntaxhighlighter table,.syntaxhighlighter table td,.syntaxhighlighter table tr,.syntaxhighlighter table tbody,.syntaxhighlighter table thead,.syntaxhighlighter table caption,.syntaxhighlighter textarea{line-height:1.3em!important}
–>
<!–
#open-tag{padding-top:8px;padding-bottom:8px;line-height:30px;border-top:2px solid #ccc;border-bottom:0 solid #e6e6e6;overflow:hidden;position:relative;margin-bottom:35px}#open-tag dd{width:755px;*width:680px}.open-tag{background-color:#f5f5f5;border:1px solid #e6e6e6;margin-right:5px;padding:1px 4px;color:#666;white-space:nowrap;text-decoration:none;display:inline-block;margin-bottom:5px;line-height:16px;vertical-align:middle}.open-tag:hover{text-decoration:underline;color:#36c}.open-tag-title{font-weight:bold;float:left;padding-right:15px;height:20px;line-height:25px}.open-tag-collapse{background:url(/static/lemma/view/img/z-ref-toggle.png) 1px 8px no-repeat;position:absolute;right:0;top:0;width:10px;height:20px;margin:10px;cursor:pointer}.collapse .open-tag-collapse{background:url(/static/lemma/view/img/z-ref-toggle.png) -9px 8px no-repeat}
–>
<!–
.basicInformation{box-shadow:0 0 5px #ddd;overflow:hidden;margin-bottom:10px;border-bottom:1px solid #ddd}#side-info{margin-bottom:0;border-bottom:0}.side-box{background-color:#f9f9f9;border:1px solid #ddd;padding-bottom:15px;margin-bottom:10px;padding:0 14px 14px}.side-box .sideLine{height:1px;background:#ddd;margin:15px 0 0 0;overflow:hidden}.side-box-extend{border:1px solid #e6e6e6;background:#fcfcfc}#card-img{position:relative;left:0;border:1px solid #ddd;background:white}#card-img .lemmapic-mask{position:absolute;display:none}.cardImgTitle{display:block;padding:8px 15px;border-left:1px solid #ddd;border-right:1px solid #ddd;color:#333;font-size:16px;font-family:”微软雅黑”;_line-height:21px}.cardImgTitle span{background:url(/static/lemma/view3/img/icon-view_5015d4f8.png) -78px -213px no-repeat;_background:url(/static/lemma/view3/img/icon-view_4b787901.gif) -78px -213px no-repeat;padding-left:31px;zoom:1}a.cardImgTitle:visited{color:#333}a.cardImgTitle:hover{color:#136ec2}#card-img-tip{width:30px;height:30px;position:absolute;right:8px;bottom:8px;background:transparent url(/static/lemma/view/img/card-img-tip.png) 0 0 no-repeat;opacity:.45}#card-img a:hover #card-img-tip{opacity:.5}#card-img a{display:block;position:relative;overflow:hidden}#info-list .gray-color{color:#555;font-weight:bold;float:left}#info-list .card-bfc{overflow:hidden;zoom:1;color:#444}#info-list dd{line-height:22px}.side-list-item{line-height:22px;color:#555}#side .city-nav{display:block;width:270px;height:125px;padding-bottom:10px}
–>
<!–
#side-auth22{border:1px solid #f1f1f1;background:white}.sidetitle{font-size:14px;font-weight:bold;color:#555;margin-bottom:10px}#side-auth{padding:0}.side-auth-img{border:1px solid #dbdbdb;background:white;display:block;float:left}.side-auth-img a{width:53px;height:53px;display:table-cell;vertical-align:middle;text-align:center;*display:block;*font-size:46px}.side-auth-img img{vertical-align:middle}.side-auth-info{width:170px;float:left;padding-left:13px}.side-auth-info p{color:#999}#authDetail{color:#999}#side-auth .whatIs{background:url(/static/lemma/view/img/lemma-top.gif) 0 -130px no-repeat;height:16px;width:16px;vertical-align:middle;display:inline-block}.authVersion{zoom:1;margin-top:15px}.authVersion span{display:block;float:left}.authVersion .divisionLine{width:1px;height:10px;background:#f1f1f1;margin:4px 10px 0;_margin-top:2px}.authVersion a{text-decoration:underline;zoom:1}#authEditVersion{text-decoration:none;color:#808080;_margin-top:1px}#authEdit,#authResource{padding:12px 15px;border:1px solid #e6e6e6;background:#fcfcfc}#authResource{margin:10px 0 0 0;overflow:hidden}
–>
<!–
#bkDynamic{padding-left:14px;padding-right:14px;margin-top:10px;padding:12px 15px;border:1px solid #e6e6e6;background:#fcfcfc}#bkDynamic .sidetitle2{color:#555;font-size:14px;font-weight:bold;margin-bottom:6px}#bkDynamic .BKdynamic-img{border-bottom:1px solid #e6e6e6;padding-bottom:10px}#bkDynamic .notice dd{font-size:12px;background:url(http://img.baidu.com/img/baike/bgs3.png) no-repeat 2px -99px;padding-left:12px;line-height:22px}#bkDynamic .notice dd a:link,#bkDynamic .notice dd a:visited,#bkDynamic .notice dd:hover{color:#666}#bkDynamic .notice dd:hover{text-decoration:underline}
–>
