凸包的graham演算法
『壹』 凸包平面凸包求法
在計算幾何中，凸包（Convex Hull）是一個重要概念，它是指二維平面上給定點集最外層的凸多邊形。Graham's Scan演算法是求解這個問題的經典方法，由數學家Graham發明，他同時也是多個學術組織的主席。（這位科學家才華橫溢，不僅在數學領域有建樹，還涉足雜技藝術。）
該演算法步驟如下：
- 首先，選擇所有點中y坐標最小的點H（如果有多解，選x坐標最小的），並排除坐標相同的點。然後對其他點與H構成的向量按照它們與x軸正方向的夾角（不需計算夾角，僅用向量模判斷）進行排序，從大到小（或從小到大）進行掃描。例如，如圖所示，經過排序後點的添加順序為H, K, C, D, L, F, G, E, I, B, A, J，接著進行逆時針（或順時針）掃描。
- 線段總是凸包的一部分，加入C後，可能需要調整。例如，盡管是凸包，但不是，因為加入D後，才是。當添加新點時，需要檢查是否改變之前線段的旋轉方向，若改變，則之前點可能不包含在凸包內，通過向量叉積判斷。
整個過程持續到所有點都遍歷完畢，即得到凸包。演算法的時間復雜度至少為O(n log n)，空間復雜度為O(1)（直接在原數據上運算）。
除了Graham's Scan，還有Jarvis步進法和一些特殊演算法，如中心法和水平法，它們各有優劣。Graham's Scan因其簡潔性和對大部分點集的適用性，通常被認為是OIer和ACMer的最佳選擇。
『貳』 凸包的平面求法
這個演算法是由數學大師葛立恆（Graham）發明的，他曾經是美國數學學會（AMS）主席、AT&T首席科學家以及國際雜技師協會（IJA）主席。
問題
給定平面上的二維點集，求解其凸包。
過程
⒈ 在所有點中選取y坐標最小的一點H，當作基點。如果存在多個點的y坐標都為最小值，則選取x坐標最小的一點。坐標相同的點應排除。然後按照其它各點p和基點構成的向量<H,p>；與x軸的夾角進行排序，夾角由大至小進行順時針掃描，反之則進行逆時針掃描。實現中無需求得夾角，只需根據餘弦定理求出向量夾角的餘弦值即可。以下圖為例，基點為H，根據夾角由小至大排序後依次為H，K，C，D，L，F，G，E，I，B，A，J。下面進行逆時針掃描。
⒉ 線段<H,K>；一定在凸包上，接著加入C。假設線段<K,C>；也在凸包上，因為就H，K，C三點而言，它們的凸包就是由此三點所組成。但是接下來加入D時會發現，線段<K,D>；才會在凸包上，所以將線段<K,C>；排除，C點不可能是凸包。
⒊ 即當加入一點時，必須考慮到前面的線段是否會出現在凸包上。從基點開始，凸包上每條相臨的線段的旋轉方向應該一致，並與掃描的方向相反。如果發現新加的點使得新線段與上線段的旋轉方向發生變化，則可判定上一點必然不在凸包上。實現時可用向量叉積進行判斷，設新加入的點為pn + 1，上一點為pn，再上一點為pn - 1。順時針掃描時，如果向量<pn - 1,pn>；與<pn,pn + 1>；的叉積為正（逆時針掃描判斷是否為負），則將上一點刪除。刪除過程需要回溯，將之前所有叉積符號相反的點都刪除，然後將新點加入凸包。
在上圖中，加入K點時，由於線段<H,C>要旋轉到<H,K>的角度，為順時針旋轉，所以C點不在凸包上，應該刪除，保留K點。接著加入D點，由於線段<K,D>要旋轉到<H,K>的角度，為逆時針旋轉，故D點保留。按照上述步驟進行掃描，直到點集中所有的點都遍歷完成，即得到凸包。
復雜度
這個演算法可以直接在原數據上進行運算，因此空間復雜度為O⑴。但如果將凸包的結果存儲到另一數組中，則可能在代碼級別進行優化。由於在掃描凸包前要進行排序，因此時間復雜度至少為快速排序的O(nlgn）。後面的掃描過程復雜度為O(n），因此整個演算法的復雜度為O(nlgn）。 對於一個有三個或以上點的點集Q，過程如下：
計算點集最右邊的點為凸包的頂點的起點，如上圖的P3點。
Do
For i = 0 To 總頂點數
計算有向向量P3->Pi
If 其餘頂點全部在有向向量P3->Pi的左側或右側，則Pi點為凸包的下一頂點
Pi點加入凸包列表
GoTo 1
End If
Next
Exit Do
1:
Loop
此過程執行後，點按極角自動順時針或逆時針排序，只需要按任意兩點的次序就可以了。而左側或右側的判斷可以用前述的矢量點積性質實現。 constpi=3.1415926575;zero=1e-6;maxn=1000;maxnum=100000000;varans,temp:extended;n,tot:longint;x,y:array[0..maxn]ofextended;zz,num:array[0..maxn]oflongint;procereswap(varii,jj:extended);vart:extended;begint:=ii;ii:=jj;jj:=t;end;procereinit;vari,j:longint;beginreadln(n);fori:=1tondoreadln(x[i],y[i]);end;functionok(x,midx,y,midy:extended):longint;beginifabs(x-midx)<=zerothenbeginifabs(midy-y)<=zerothenexit(0);ifmidy>ythenexit(1)elseexit(2);endelsebeginifx<midxthenexit(1)elseexit(2);end;end;procereqsort(head,tail:longint);vari,j:longint;midx,midy:extended;begini:=head;j:=tail;midx:=x[(head+tail)div2];midy:=y[(head+tail)div2];repeatwhileok(x[i],midx,y[i],midy)=1doinc(i);whileok(x[j],midx,y[j],midy)=2dodec(j);ifi<=jthenbeginswap(x[i],x[j]);swap(y[i],y[j]);inc(i);dec(j);end;untili>j;ifi<tailthenqsort(i,tail);ifj>headthenqsort(head,j);end;functionPlot(x1,y1,x2,y2:extended):extended;beginPlot:=x1*y2-x2*y1;end;functioncheck(first,last,new:longint):boolean;varax,ay,bx,by:extended;Pt:extended;beginax:=x[last]-x[first];ay:=y[last]-y[first];bx:=x[new]-x[first];by:=y[new]-y[first];ifPlot(ax,ay,bx,by)<=0thenexit(true)elseexit(false);end;procereTbao;vari,j,tail:longint;begintot:=0;zz[1]:=1;tail:=1;fori:=2tondobeginwhile(zz[tail]<>1)andcheck(zz[tail-1],zz[tail],i)dodec(tail);inc(tail);zz[tail]:=i;end;inc(tot,tail-1);fori:=1totail-1donum[i]:=zz[i];zz[1]:=n;tail:=1;fori:=n-1downto1dobeginwhile(zz[tail]<>n)andcheck(zz[tail-1],zz[tail],i)dodec(tail);inc(tail);zz[tail]:=i;end;fori:=1totail-1donum[tot+i]:=zz[i];inc(tot,tail-1);end;functiondist(a,b:longint):extended;begindist:=sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));end;proceremain;vari,j:longint;beginqsort(1,n);Tbao;ans:=0;fori:=1totot-1doans:=ans+dist(num[i],num[i+1]);ans:=ans+dist(num[tot],num[1]）;ans:=ans+temp*pi*2;writeln(ans:0:1);end;begininit;main;end.
