812.最大三角形面积

题目

最大三角形面积

思路

暴力解法：三重循环。主要是计算三角形面积的公式

题解

• 题解1

class Solution {
public:
    double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
        return 0.5 * abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
    }

    double largestTriangleArea(vector<vector<int>> & points) {
        int n = points.size();
        double ret = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ret = max(ret, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
                }
            }
        }
        return ret;
    }
};

• 时间复杂度：O(n ^ 3)，其中 n 是数组中元素的个数
• 空间复杂度：O(1)

执行用时：8 ms, 在所有 C++ 提交中击败了78.81%的用户

内存消耗：7.4 MB, 在所有 C++ 提交中击败了54.24%的用户

通过测试用例：57 / 57