题解 | #最大四边形面积#

题目描述
给定大小为n的整数集合A，代表n根木棍的长度。从A中任选4根木棍组成一个四边形，求其面积最大为多少。数据保证有解。
程序返回结果与正确答案的误差应小于0.00001

方法一：暴力方法

求解思路
对于求解本题目，我们应首先知道构成四边形的充要条件为三边之和大于第四边，并且在四边已知的情况下四边形的最大面积为 $图片说明$ ，其中sum=(a+b+c+d)/2.
根据以上条件，我们将题目所给的数组进行遍历，首先判断是否否成四边形，若构成四边形则计算其最大面积，最后输出结果即可。

图片说明

解题代码

class Solution {
public:
    double square(int a, int b, int c, int d)
    {   //判断四边形是否存在且计算面积
        if(a + b + c < d || a + b + d < c || a + c + d < b || b + c + d < a) // 三边之和要大于第四边
            return 0.0;
        double sum = ((double) (a + b + c + d))/ 2;
        return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); // 计算面积
    }
    double solve(vector<int>& a)
    {
        int n = a.size();
        double hyres = 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++)
                    for(int m = k + 1; m < n; m++)
                        hyres = max(hyres, square(a[i], a[j], a[k], a[m]));
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：四层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存空间，因此空间复杂度为 $O(1)$

方法二：优化方法--排序思想

求解思路
对于方法一，我们对其进行改进，因为最大的四边形，边长我们选较大的，最后可能会得到面积最大的四边形，因此我们对数组进行排序，然后从后往前选取，输出第一个计算得到的四边形面积即是题目所要求的结果。

图片说明

解题代码

class Solution {
public:
    double solve(vector<int>& a)
    {
        sort(a.begin(), a.end()); // 排序
        int n = a.size();
        double myres = 0.0;
        for(int i = n - 1; i >= 0; i--) // 选取最后四个能组成四边形的组合
            for(int j = i - 1; j >= 0; j--)
                for(int k = j - 1; k >= 0; k--)
                    for(int m = k - 1; m >= 0; m--)
                    {
                        int aa = a[i];
                        int b = a[j];
                        int c = a[k];
                        int d = a[m];
                        if(aa + b + c > d && aa + b + d > c && aa + c + d > b && b + c + d > aa)
                        {
                            double sum = ((double) (aa + b + c + d)) / 2;
                            myres = sqrt((sum - aa) * (sum - b) * (sum - c) * (sum -d));
                            return myres;
                        }
                    }
        return myres;//返回第一个计算出来的四边形的面积
    }
};

复杂度分析
时间复杂度：四层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$