求最小凸包

——Graham算法——凸包概念凸包（ConvexHull）是一個計算幾何（圖形學）中的概念。用不嚴謹的話來講，給定二維平面上的點集，凸包就是將最外層的點連接起來構成的凸多邊型，它能包含點集中所有點的。

這個算法是由數學大師葛立恒(Graham)發明的，他曾經是美國數學學會主席，AT&T首席科學家以及國際雜技師協會主席。Graham算法是在某種意義上來說求解二維靜態凸包的一種最優的算法，這種算法目前被廣泛的應用于對各種以二維靜態凸包為基礎的ACM題目的求解。Graham算法的時間復雜度大約是nlogn,因此在求解二維平面上多個點構成的凸包時，消耗時間相對較少。Graham_scan算法1.在所有點中選取y坐標最小的一點H，當作基點。如果存在多個點的y坐標都為最小值，則選取x坐標最小的一點。坐標相同的點應排除。Graham_scan算法H2.然后按照其它各點p和基點構成的向量<H,p>與x軸的夾角進行排序，夾角由小到大進行逆時針掃描。并依次排序。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p53.將P0,P1,p2放入棧中。并將棧內的點依次排號并命名為Ai（i以0為起點）,P0,P1必為凸包的兩點Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p53.以P1為基點，判斷P1P2P3是否為逆時針方向，若是，P3進棧。再A2以為基點，判斷A2A3P4。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p3A3p53.以A2為基點，判斷A2A3P4是否為逆時針方向，若是，P4進棧,若不是，P3出棧，P4進棧。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P4（進）A3p5（出棧）（入棧）P3（出）3.繼續以A2為基點，判斷A2A3P5是否為逆時針方向。若是，P5進棧，若不是，P4出棧，P5進棧。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P5（進棧）A3P5P4(出棧)3.繼續以A2為基點，判斷A2A3P6,可知A2A3P6為逆時針方向，故A6進棧。Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4（保存）（進棧）4.以A3為基點，判斷A3A4P7,按照前面的方法，可得保存P6，P7進棧；Graham_scan算法H（P0）p10p8p9p7P6(保存)P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p7A55.按照此方法，可得棧中的點依次為：Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p10A5p11p12p14A6A7A8幾何中心算法H（P0）p10p8p9p7P6P4P