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

最大四边形面积

http://www.nowcoder.com/practice/0eaf4653f1d243d4a46b3d5d60a7362e

最大四边形面积

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

示例

输入：[1,2,3,4,5]

返回值：10.95445

方法一

思路分析

本题可以直接使用暴力搜索的办法，即设置四层循环，每次找到四条边的长度，先判断是否可以构成四边形，而后计算四边形的面积。
判断构成四边形的条件：三边之和大于第四边
四边形的最大面积：

$\\s= \sqrt{(p-a)(p-b)(p-c)(p-d)} \\p=(a+b+c+d)/2$

图解

四层循环遍历找到符合条件的最优解

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    bool judge(int a,int b,int c,int d)
	{
		int total = a+b+c+d;
		int maxn = max(a,b);
		maxn = max(maxn,c);
		maxn = max(maxn,d);
		if(total > 2*maxn) //判断能否构成四边形 
			return true;
		return false;
	}
    double square(int a, int b, int c, int d){ 
        if(!judge(a,b,c,d)) 
            return 0.0;
        double sum = ((double) (a + b + c + d))/ 2.0;
        return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); //计算面积
    }
    double solve(vector<int>& a) {
        int n = a.size();
        double res = 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++)
                        res = max(res, square(a[i], a[j], a[k], a[m]));
        return res;
    }
};

复杂度分析

时间复杂度：设置了四层嵌套循环，循环次数为 $\sum_{i=0}^{n-1}{(n-i)*(n-i-1)*(n-i-2)} =n*(n-1)*(n-2)+(n-1)*(n-2)*(n-3)+...+1*2*3$ ，即从$n$个数中找到4个元素，因此时间复杂度最大为 $O(C_{n}^{4})$
空间复杂度：空间复杂度为$O(1)$

方法二

思路分析

方法一中没有对给定的数组元素排序，要想得到最大的四边形的，首先对数组元素降序排序，然后循环遍历找到第一个可以构成四边形的四个边，然后输出其最大面积。

图解

对数组元素降序排序后，从第四个元素出发循环遍历，与之前三个元素构成四边形的四条边，如果可以构成那么计算其面积，这样挑出的边是最长的，那么面积是最大的，即可输出结果

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    static bool cmp(int a,int b)
    {
        return a>b;
    }
    bool judge(int a,int b,int c,int d)
	{
		int total = a+b+c+d;
		int maxn = max(a,b);
		maxn = max(maxn,c);
		maxn = max(maxn,d);
		if(total > 2*maxn) //判断能否构成四边形 
			return true;
		return false;
	}
    double square(int a, int b, int c, int d)
    { 
        double sum = ((double) (a + b + c + d))/ 2.0;
        return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); //计算面积
    }
    double solve(vector<int>& a) {
        // write code here
        sort(a.begin(), a.end(),cmp);//首先从大到小排序
        int n=a.size();
        for (int i = 3; i < n; ++i) 
        {
            int j=a[i-3];
            int k=a[i-2];
            int l=a[i-1];
            int m=a[i];
            if (judge(j,k,l,m)) 
            {
                return square(j,k,l,m);
            }
        }
        return 0;
    }
};