几何

凸包面积

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

const int maxn = 1005;
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;
}

bool direction(node a, node b, node c)
{
    // 向量ab的坐标
    int x1 = b.x - a.x;
    int y1 = b.y - a.y;
    // 向量ac的坐标
    int x2 = c.x - a.x;
    int y2 = c.y - a.y;
    if (x1 * y2 - x2 * y1 > 0)
        return true; // ab在ac的顺时针方向
    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++)
    {
        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;
        }
    }
    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);
        printf("%.1lf\n", area);
    }

    return 0;
}