求凸包面積（分治法）

求凸包面積的方式有很多，本次我所講的是利用分支法來求解該題，其它就不在講述~~(狗頭)~~,大部分都瞭解分治法是將大問題化成小問題求解，恰恰好這種求凸包面積很適合用分支法，個人覺得這樣程式碼較短

下面結合著例題講解：

麥兜是個淘氣的孩子。一天，他在玩鋼筆的時候把墨水灑在了白色的牆上。再過一會，麥兜媽就要回來了，麥兜為了不讓媽媽知道這件事情，就想用一個白色的凸多邊形把牆上的墨點蓋住。你能告訴麥兜最小需要面積多大的凸多邊形才能把這些墨點蓋住嗎？ 現在，給出了這些墨點的座標，請幫助麥兜計算出覆蓋這些墨點的最小凸多邊形的面積。

輸入:

多組測試資料。第一行是一個整數T，表明一共有T組測試資料。
每組測試資料的第一行是一個正整數N(0< N < = 105)，表明了墨點的數量。接下來的N行每行包含了兩個整數Xi和Yi（0<=Xi,Yi<=2000），表示每個墨點的座標。每行的座標間可能包含多個空格。

輸出:

每行輸出一組測試資料的結果，只需輸出最小凸多邊形的面積。面積是個實數，小數點後面保留一位即可，不需要多餘的空格。

樣例輸入
2
4
0 0
1 0
0 1
1 1
2
0 0
0 1
樣例輸出
1.0
0.0

先上程式碼吧，可能我的程式碼比我的講解更清楚(自嘲)

#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
const int maxn = 1001;
// 記錄結果
double area = 0.0;
struct node{
    int x;
    int y;
}a[maxn];
bool cmp(node a, node b) {
    if(a.x != b.x) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

// 根據叉乘判斷方向
// 判斷ac向量在ab向量的順時針方向還是逆時針方向
// 返回 true表示逆時針方向
// 返回 false表示順時針方向
bool direction(node a, node b, node c) {
    // ab向量的座標
    int x1 = b.x - a.x;
    int y1 = b.y - a.x;
    // ac向量的座標
    int x2 = c.x - a.x;
    int y2 = c.y - a.y;
    if(x1 * y2 - y1 * x2 > 0)
        return true;
    return false;
}

/*
    求任意三個點連線圍成的三角形的面積
*/
double getArea(node a, node b, node c) {
    // 根據行列式的性質可知，三角形的面積等於三階行列式的一半
    return fabs(0.5 * (a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y));
}
/*
    計算上下凸包的面積，當flag=true,求凸包上半部分的面積
                        當flag=false，求凸包下半部分的面積
    left, right 分別表示凸包區間的左右端點的橫座標，利用分治法進一步求其
    整個凸包的面積
*/
void caculate(bool flag, int left, int right) {
    /*
        迴圈遍歷的left，right之間的每個點，在left和right指定的一側時
        並且求其最大面積
    */
    double temp = -1.0;
    int k = 0; // 記錄面積最大的那個點的橫座標
    for(int i = left + 1; i <= right - 1; i++)
    {
        // 判斷當上下凸包時，該點是否在left和right連線指定的一側，如果沒在就不考慮該點
        if(direction(a[left], a[right], a[i]) != flag) {
            continue;
        }
        if(temp < getArea(a[left], a[right], a[i])) {
            temp = getArea(a[left], a[right], a[i]);
            k = i;
        }
    }
    // 當k沒有改變證明此時只有兩個點不構成三角形，故結束遞迴
    if(k == 0)
        return;
    area += temp;
    caculate(flag, left, k);
    caculate(flag, k, right);
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        area = 0.0;
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i].x >> a[i].y;
        }
        sort(a + 1, a + n + 1, cmp);
        // 求上凸包的面積
        caculate(true, 1, n);
        // 求下凸包的面積
        caculate(false,1, n);
        cout << fixed << setprecision(1);
        cout << area << endl;
    }
    return 0;
}

相信看了以上的程式碼大概的有一些自己的思路了吧，就我而言，我所理解的凸包就把一個一個的點看成一個一個的釘子，這時用一個皮筋給它包住，此時這個皮筋就是凸包的邊界。對於求這個題我們最重要的就是找到那些點是屬於凸包的點。剛開始將各個頂點排序，我們可以想到橫座標最小和最大的點一定是凸包的頂點。

找到左右兩個端點後我們將其分為上下兩部分分開算，上下兩個部分分別進行遞迴，求出其各個面積。首先考慮上部分，對於上部分，要確定那個點是凸包的點我們立即就可以想到離AB直線最遠的點一定是凸包的頂點，換而言之就是在上半部分找到一個點使得該點與AB兩點組成的三角形面積最大，計算出該面積

假設C點是距離AB最遠的點，計算出三角形ABC的面積，這是三角形ABC裡面的點的面積就不用管了，是不是對於直線AB上部分我們是不是求出了一些面積了（三角形ABC的面積），剩下的就是直線AC的外側的和BC外側的點的面積沒有求了，其實你你理解了上面的做法，接下來就很容易啦，用同樣的方法求直線AC和BC外的凸包的點。好啦，本次求凸包的面積就講完了，是不是感覺結束的很突兀，如還有疑問的話可以私信博主本人額