# 凸包
###### tags: `Competitive Programming Note` `108 師大附中校隊培訓`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

[108 師大附中校隊培訓簡報](/@wiwiho/BJ-VDAXcr)

你有一大堆點，然後你要找出一個可以圍住這些點且面積最小的凸多邊形，這個凸多邊形稱為凸包。

顯而易見，如果要面積最小，那凸包的頂點勢必得是這一大堆點的其中幾個點，你也可以想成是用一條橡皮筋把這些點圈起來。


那麼，如何有效率地把凸包蓋出來呢？

先把各個點按 $x$ 座標由小到大排序，$x$ 座標相同則再按 $y$ 座標由小到大排序，排序之後的點順序會是由左至右、由上至下，這樣一來我們就可以按這個順序遍歷這些點，這種往固定方向掃描的方式，稱為掃描線。


知道點的左右上下關係可以幹嘛？

先討論一件事情：有一個凸多邊形，它的頂點已經按逆時針順序排好了，依序是 $p_0p_1p_2...p_{n-1}$，那麼 $p_i$ 和 $p_{i+1}$ 與 $p_{i+2}$ 的關係會是什麼（令 $p_i=p_{i \bmod n}$）？既然是凸多邊形，那麼它的邊應該要是一直往同個方向轉彎的，而如果將邊逆時針排序，這個邊的斜率也應該是一直往逆時針方向轉彎，顯然點也會是這樣，因此：
$$\overrightarrow{p_ip_{i+1}}\times\overrightarrow{p_ip_{i+2}} > 0$$


再來，我們把凸包分成上下兩部分：上凸包和下凸包，以極左和極右點分割，如果極左點或極右點有兩個（最多只會有兩個），上面那個屬於上凸包，下面那個屬於下凸包，否則極左點必屬於下凸包，極右點必屬於上凸包。


顯然，上或下凸包中不會有 $x$ 座標相同的頂點，因此在上或下凸包中，每個頂點都能分別出左右的關係，並且你會發現，如果把點按逆時針排序，在下凸包中的點也是由左而右排序的、在上凸包的點也是由右而左排序的。

這樣一來左右關係就有用了，先用由左而右的掃描線把下凸包做出來，再用由右而左的掃描線把上凸包做出來，就可以得到整個凸包。

這整個流程可以用一個 stack 來實作，在處理一個點的時候，我們嘗試把它加進凸包裡，此時這個點是 $p_{i+2}$，堆頂的點是 $p_{i+1}$，堆頂再往下一個點是 $p_{i}$，把這些點代入剛剛的式子，符合條件或者 stack 大小小於 $2$ 時就停止，否則就把堆頂 pop，然後繼續重複，結束之後就把目前處理中的點放入堆頂。

在做下凸包的時候，先從最左邊且最下面的點開始做上述動作，做到最後，堆頂的點應該會是最右邊且最上面的點，把它 pop 掉，因為它應該屬於上凸包；做上凸包的時候，從最右邊且最上面的點開始做，最後堆頂會是最左且最下的點，把它 pop 掉後，這兩個接起來就是完整的凸包。

因為要用到堆頂往下一個點，所以 stack 用 vector 來實作。

#include <bits/stdc++.h>

#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define F first
#define S second

using namespace std;

template<typename T>
pair<T, T> operator-(pair<T, T> a, pair<T, T> b){
    return mp(a.F - b.F, a.S - b.S);
}

template<typename T>
T cross(pair<T, T> a, pair<T, T> b){
    return a.F * b.S - a.S * b.F;
}

template<typename T>
vector<pair<T, T>> getConvexHull(vector<pair<T, T>>& pnts){

    int n = pnts.size();
    sort(pnts.begin(), pnts.end());

    vector<pair<T, T>> hull;

    for(int i = 0; i < 2; i++){
        int t = hull.size();
        for(pair<T, T> pnt : pnts){
            while(hull.size() - t >= 2 && cross(hull.back() - hull[hull.size() - 2], pnt - hull[hull.size() - 2]) <= 0)
                hull.pop_back();
            hull.pb(pnt);
        }
        hull.pop_back();
        reverse(pnts.begin(), pnts.end());
    }

    return hull;
}

這個演算法叫 Andrew's monotone chain，另一種比較常聽到的凸包演算法是 Graham's scan，有興趣可以自己查。

## 練習題

- [TIOJ 1178](https://tioj.ck.tp.edu.tw/problems/1178) - 給一堆點，求凸包的頂點數量
- [ZeroJudge a871](https://zerojudge.tw/ShowProblem?problemid=a871) - 求凸多邊形面積（點不一定照順序）
- [ZeroJudge d546](https://zerojudge.tw/ShowProblem?problemid=d546) - 求多邊形面積和凸包面積差
- [TIOJ 1280](https://tioj.ck.tp.edu.tw/problems/1280) - 給你一堆點，求所有點對連成的直線所能圍出的最大面積