定義 ============= 在散所有散佈點中,找出一個凸多邊形可以剛好包含所有的點
像下圖所示
![alt text](/convex_hull.png) 演算法介紹 ============= 有三種方法來找出凸多邊形 Brute Force ------------- 說明:
此方法為暴力解,先選擇任意兩個點構成線
假設其他的點都在那條線的左邊(or右邊, 固定一邊)
則此邊為我們要的邊

![alt text](/acm/Brute Force.png)

pseudo code:
```c++ Algorithm CH(P) E←∅(* edge-list of CH(P) *) for all ordered pairs (p,q) ∈ p×p, p≠q do supporting ← true for all points r ∈ P-{p,q} do if r is on the right side of pq then supporting ← false if supporting then add directed edge pq to E From the (un-ordered) edge-list E, construct the list of vertices of CH(P) in CCW order in O(n) time. (How?) end ```
複雜度:O(n³) Graham-Scan ------------- 說明:
1.選定起始點,利用起始點跟其他點連線所構成的角度,去sort各個點

![alt text](/acm/Graham-Scan-1.png)

Compare Function:
```c++ bool compare_angle(Point& a, Point& b) { // 角度相同時,距離長度的判斷。 int c = cross(P[0], a, b); return c > 0 || (c == 0 && length2(P[0], a) < length2(P[0], b)); } ```
2.再開始一個一個點連線,假設有依照順序連到了P3, 就要檢查往前數的第二點P1
,此點與p2, 和p3的外積,如果外積小於0,p3就要連回p1(如下圖所示),如果大於0,就不變
![alt text](/Graham-Scan-2.png)
3.完成後的圖形

![alt text](/acm/Graham-Scan-3.png)

4.Pseudo code
```c++ Graham-Scan(Q) void Graham_scan() { //將最左下的點移到起點 swap(P[0], min_element); // 其餘各點依角度排序。O(NlogN) sort(P+1, P+N, compare_angle); // 直接把中心點作為起點,開始包覆,逆時針方向。 O(N)P[N] = P[0]; // 讓程式方便處理包至最後一點的情況。 for (int i=0; i<=N; ++i){ // 掃除凹陷的點 // 添加新的點 // 扣掉最後一個點 } ``` Andrew's Monotone Chain ---------------------------- >step1:將所有點按座標大小排序
>step2:將下半部圍起來
>step3:維持下半部不動,將上半部圍起來
>step4:刪去重複的起點 ------------------------------ STEP1: 依照每個點的x座標進行排序
![alt text](/Andrew's Monotone Chain step1.png) STEP2: ```c++ int m=0; for(int i=0; i=2 && cross(CH[m-2], CH[m-1], P[i] <= 0) m--; CH[m++] = P[i]; } ```
![link label](/acmstep2) STEP3: ```c++ for(int i=N-2, t=m+1; i>=0; --i) { while(m>=t && cross(CH[m-2], CH[m-1], P[i] <= 0) m--; CH[m++] = P[i]; } ```
![alt text](/step3.png) STEP4:刪除最後一個點
![alt text](/step4.png)