求凸包面积（分治法）

求凸包面积的方式有很多，本次我所讲的是利用分支法来求解该题，其它就不在讲述~~(狗头)~~,大部分都了解分治法是将大问题化成小问题求解，恰恰好这种求凸包面积很适合用分支法，个人觉得这样代码较短

下面结合着例题讲解：

麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最小需要面积多大的凸多边形才能把这些墨点盖住吗？ 现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。

输入:

多组测试数据。第一行是一个整数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));
}

void caculate(bool flag, int left, int 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外的凸包的点。好啦，本次求凸包的面积就讲完了，是不是感觉结束的很突兀，如还有疑问的话可以私信博主本人额