凸包

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

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

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

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

先把各個點按

$x$ 座標由小到大排序，

$x$ 座標相同則再按

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

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

先討論一件事情：有一個凸多邊形，它的頂點已經按逆時針順序排好了，依序是

$p_0{p}_1{p}_2...p_{n-1}$，那麼

$p_i$ 和

$p_{i+1}$ 與

$p_{i+2}$ 的關係會是什麼（令

$p_i=p_{imodn}$）？既然是凸多邊形，那麼它的邊應該要是一直往同個方向轉彎的，而如果將邊逆時針排序，這個邊的斜率也應該是一直往逆時針方向轉彎，顯然點也會是這樣，因此：

$$\overrightarrow{p_i{p}_{i+1}}\times \overrightarrow{p_i{p}_{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 - 給一堆點，求凸包的頂點數量
• ZeroJudge a871 - 求凸多邊形面積（點不一定照順序）
• ZeroJudge d546 - 求多邊形面積和凸包面積差
• TIOJ 1280 - 給你一堆點，求所有點對連成的直線所能圍出的最大面積