求凸包——Graham扫描算法

——————byMBA智库 http://wiki.mbalib.com/wiki/凸包

算法

这里就介绍一个Graham扫描算法

Graham扫描法

　由最底的一点A1开始，计算它跟其他各点的连线和x轴的角度，按小至大将这些角度排序，称它们的对应点为A_2,A_3,\ldots,A_n。这里的时间复杂度可达O(nlogn)。

　考虑最小的角度对应的点A3。若由A2到A3的路径相对A1到A2的路径是向右转的（可以想象一个人沿A1走到A2，他站在A2时，是向哪边改变方向），表示A3不可能是凸包上的一点，考虑下一点由A2到A4的路径；否则就考虑A3到A4的路径是否向右转……直到回到A1。

　这个算法的整体时间复杂度是O(nlogn)，注意每点只会被考虑一次，而不像Jarvis步进法中会考虑多次。

　这个算法由葛立恒在1972年发明。它的缺点是不能推广到二维以上的情况。

代码如下：

#include<cstdio> #include<stack> #include<algorithm> #include<cmath> using namespace std; const int maxn = 1000; struct Node{ int x,y; }u,node[maxn]; int N; int cmp1(const Node &a, const Node &b) { return a.y < b.y; } /*极角排序*/ int cmp2(const Node &a, const Node &b) { return atan2(1.0*(a.y-u.y), 1.0*(a.x-u.x)) < atan2(1.0*(b.y-u.y), 1.0*(b.x-u.x)); } /*计算叉积*/ int Direction(Node a, Node b, Node c) { return (c.x-a.x) * (b.y-a.y) - (b.x-a.x) * (c.y - a.y); } /*判断是否向右*/ bool right(Node a, Node b, Node c) { if(Direction(a, b, c) < 0) { return true; } else return false; } int main() { scanf("%d",&N); for(int i=0; i<N; i++) { scanf("%d%d",&node[i].x, &node[i].y); } sort(node, node+N, cmp1); stack<Node> s; s.push(node[0]); u = node[0]; sort(node+1, node+N, cmp2); s.push(node[1]); s.push(node[2]); for(int i=3; i<N; i++) { Node top = s.top(); s.pop(); Node n_top = s.top(); if(right(node[i], top, n_top)) { s.push(node[i]); } else{ s.push(top); s.push(node[i]); } } while(!s.empty()) { printf("%d %d\n",s.top().x, s.top().y); s.pop(); } return 0; }