【05-15】力扣每日一题

最近事情比较多，今天的每日一题就简单说一说吧。
本文首发于馆主君晓的博客，05-15

题目内容

  题目链接，812. 最大三角形面积，题目截图如下：

题目分析

  这道题目就是给你一串点的集合，然后你任选三个点，找出能够组成的三角形，并且返回三角形面积最大的值。这道题其实有很多种方法可以实现，具体的可以去力扣官方题解查看详细内容。这里我介绍一种使用高中知识就能够做出来的方法，当然思路还是暴力遍历，枚举所有的三个点的组合，然后判断是否能够形成三角形，如果能够形成三角形（任意两边之和大于第三边），之后我们就计算余弦值，举个栗子，如下图所示，我想说应该很通俗易懂吧，使用三角函数的方法来计算我们的三角形面积。

代码实现

  c++代码实现如下：

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        // 直接暴力三重循环
        double res = 0.0;
        for(int i = 0;i<points.size()-2;i++){
            for(int j = i+1;j<points.size()-1;j++){
                for(int k = j+1;k<points.size();k++){
                    int point_a[2] = {points[i][0],points[i][1]};
                    int point_b[2] = {points[j][0],points[j][1]};
                    int point_c[2] = {points[k][0],points[k][1]};
                    // 开始计算三边的长度
                    double ab = sqrt(pow(point_a[0]-point_b[0],2)+pow(point_a[1]-point_b[1],2));
                    double bc = sqrt(pow(point_b[0]-point_c[0],2)+pow(point_b[1]-point_c[1],2));
                    double ac = sqrt(pow(point_a[0]-point_c[0],2)+pow(point_a[1]-point_c[1],2));
                    // 判断能否组成三角形
                    if(ab+bc<=ac || ab+ac<=bc || bc+ac<=ab){
                        continue;
                    }
                    // 现在能够组成三角形 那就计算面积 1/2 bc Sin A
                    double cosa = (ac*ac+ab*ab-bc*bc)/(2*ab*ac);
                    double s = sqrt(0.25*(ac*ac)*(ab*ab)*(1-cosa*cosa));
                    if(s>res){
                        res = s;
                    }
                }
            }
        }
        return res;
    }
};

结语

  为有牺牲多壮志，敢叫日月换新天！