algo-aha

一些点按顺序能否构成凸包

只要判断每三个点顺序构成的两向量都向一个方向拐。判断两向量向哪个方向拐，只要看叉积：>0逆时针、<0顺时针、=0共线。

向量a和b的叉积\[a \times b = \begin{vmatrix} x_1 & x_2 \ y_1 & y_2 \end{vmatrix} = x_1y_2 - x_2y_1\]

• https://leetcode.com/problems/convex-polygon

bool isConvex(vector<vector<int>>& points) {
    const int N = points.size();
    if (N < 3) return false;

    int prev = 0;
    for (int i = 0; i < N; i++) {
        int curr = getDirection(points[i], points[(i+1) % N], points[(i+2) % N]);
        if (curr == 0) continue;
        if (prev == 0) prev = curr;
        else if (curr != prev) return false;
    }
    return true;
}

int getDirection(const vector<int> &x, const vector<int> &y, const vector<int> &z) {
    // x、y、z三点构成a、b两向量，计算a、b的叉积，返回1、-1、0表示拐向
    vector<int> a = { y[0] - x[0], y[1] - x[1] };
    vector<int> b = { z[0] - y[0], z[1] - y[1] };
    int crossProd = a[0] * b[1] - a[1] * b[0];
    return crossProd > 0 ? 1 : (crossProd < 0 ? -1 : 0);
}

最大三角形面积

• https://leetcode.com/problems/largest-triangle-area/

double largestTriangleArea(vector<vector<int>>& points) {
    const int N = points.size();
    double ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                ans = max(ans, area(points[i], points[j], points[k]));
            }
        }
    }
    return ans;
}

double area(const vector<int> &x, const vector<int> &y, const vector<int> &z) {
    // x、y、z三点可以构造x->y向量a、y->z向量b，计算a、b的叉积
    // 根据平行四边形面积=abs(叉积)，三角形面积=abs(叉积)*0.5
    vector<int> a = { y[0]-x[0], y[1]-x[1] };
    vector<int> b = { z[0]-y[0], z[1]-y[1] };
    int crossProd = a[0] * b[1] - a[1] * b[0];
    return abs(crossProd) * 0.5;
}