凸包（Convex Hull）是一個計(jì)算幾何（圖形學(xué)）中的概念。在一個實(shí)數(shù)向量空間中礁芦，對于給定集合X堂氯，所有包含X的凸集的交集S被稱為X的凸包腺兴。X的凸包可以用X內(nèi)所有點(diǎn)(X1左电，...Xn)的凸組合來構(gòu)造。在二維歐幾里得空間中页响，凸包可想象為一條剛好包著所有點(diǎn)的橡皮圈篓足。用不嚴(yán)謹(jǐn)?shù)脑拋碇v，給定二維平面上的點(diǎn)集闰蚕，凸包就是將最外層的點(diǎn)連接起來構(gòu)成的凸多邊型栈拖，它能包含點(diǎn)集中所有的點(diǎn)。
Graham掃描法
image.png
- 將隨機(jī)生成的點(diǎn)放在一個平面直角坐標(biāo)系中没陡，Y 軸中最小的點(diǎn)一定是凸包上面的點(diǎn)涩哟，并以此作為坐標(biāo)的原點(diǎn)則P0。
- 以P0作為頂角盼玄，X 軸作為一條邊其他頂點(diǎn)與 P0 連接生成第三邊例如∠P1P0X 贴彼。
- 計(jì)算各個點(diǎn)相對于 P0 的幅角 α ，按從小到大的順序?qū)Ω鱾€點(diǎn)排序强岸。很容易得知 P1 和 P8 必為凸包上的點(diǎn)。當(dāng)幅角 α 相同時(shí)將靠近P0的點(diǎn)排在前面砾赔。
- 將凸包上的點(diǎn)入棧蝌箍，如 P1 入棧青灼，并將 P0 與棧頂元素連接如 P0-P1。判斷Pn+1 在 PO 與棧頂連線 L 的左邊還是右邊妓盲。如果在左邊或在同一直線上時(shí)即將它與棧頂元素相連杂拨，顯然 P2 與 P1連接。
- 將新連接線段的坐標(biāo)與前一線段坐標(biāo)進(jìn)行叉積運(yùn)算悯衬，如果叉積結(jié)果為負(fù)則必為凸包上的點(diǎn)將其入棧否則出棧弹沽，如果棧頂元素不是 幅角 α 最大的元素繼續(xù)執(zhí)行步驟4，否則結(jié)束當(dāng)前棧中元素即為凸包上的頂點(diǎn)筋粗。
- 例如
按步驟 4 的做法已將P1 P2 P3 連接策橘，{P1，P2}娜亿，{P2丽已，P3} 進(jìn)行叉積，所得到的結(jié)果為 + 則 P2 不是凸包上的點(diǎn)出棧买决，P3進(jìn)棧返回執(zhí)行步驟4沛婴。則需要判斷 {Pn-1,Pn} {Pn,Pn+1} 的叉積。
矢量叉積定義
矢量叉積
設(shè)有點(diǎn)p0(x0,y0),p1(x1,y1),p2(x2,y2).（p0p1）,（p0p2）是共p0的兩條向量督赤，叉積d = （p0p1）x(p0p2) = (x1-x0)(y2-y0) - (x2-x0)(y1-y0)
叉積的一個非常重要性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時(shí)針關(guān)系：
若 d > 0 , 則(p0p1)在(p0p2)的順時(shí)針方向嘁灯。
若 d < 0 , 則(p0p1)在(p0p2)的逆時(shí)針方向。(圖示方向)
若 d = 0 , 則(p0p1)與(p0p2)共線躲舌，但可能同向也可能反向丑婿。
實(shí)現(xiàn)代碼
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<stack>
6 #include <math.h>
7 #include <stdio.h>
8 #include <algorithm>
9 using namespace std;
10 struct point
11 {
12 long long x;
13 long long y;
14 } P[50005],S[50005]; //P 中存點(diǎn)，S模擬棧存凸包的點(diǎn)孽糖；
15
16 long long xx;
17 long long yy;
18
19 // 計(jì)算各個點(diǎn)相對于 P0 的幅角 α 枯冈，按從小到大的順序?qū)Ω鱾€點(diǎn)排序。當(dāng) α 相同時(shí)办悟，距離 P0 比較近的排在前面尘奏。
20 bool cmp(struct point a,struct point b)
21 {
22 if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
23 return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
24 return a.x<b.x;
25 }
26
27 //叉積判斷點(diǎn)的位置
28 long long CJ(long long x1,long long y1,long long x2,long long y2)
29 {
30 return (x1*y2-x2*y1);
31 }
32
33 long long Compare(struct point a,struct point b,struct point c)
34 {
35 return CJ((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
36 }
37
38
39 int main()
40 {
41 int n,i,j;
42 while(~scanf("%d",&n))
43 {
44 int top = 1;
45 yy = 1000000+5;
46 for(i=0;i<n;i++)
47 {
48 scanf("%lld%lld",&P[i].x,&P[i].y);
49 if(P[i].y<yy)
50 {
51 yy = P[i].y;
52 xx = P[i].x;
53 j = i;
54 }
55 }
56 P[j] = P[0];
57 sort(P+1,P+n,cmp);
58 S[0].x = xx;
59 S[0].y = yy;
60 S[1] = P[1];
61 for(i = 2;i<n;)
62 {
63 if(top&&(Compare(S[top-1],S[top],P[i])<0)) top--;
64 else S[++top] = P[i++];
65 }
66 for(i=0;i<=top;i++)
67 printf("%lld %lld\n",S[i].x,S[i].y);
68 }
69 return 0;
70 }
菜雞實(shí)現(xiàn)過程可能解釋得不通順，望請見諒病蛉。
