Zu Chongzhi (429–500) was a prominent Chinese mathematician and astronomer during the Liu Song and Southern Qi Dynasties. Zu calculated the value ofπ to the precision of six decimal places and for a thousand years thereafter no subsequent mathematician computed a value this precise. Zu calculated one year as 365.24281481 days, which is very close to 365.24219878 days as we know today. He also worked on deducing the formula for the volume of a sphere.

It is said in some legend story books that when Zu was a little boy, he liked mathematical games. One day, his father gave him some wood sticks as toys. Zu Chongzhi found a interesting problem using them. He wanted to make some triangles by those sticks, and he wanted the total area of all triangles he made to be as large as possible. The rules were :

1) A triangle could only consist of 3 sticks.
2) A triangle's vertexes must be end points of sticks. A triangle's vertex couldn't be in the middle of a stick.
3) Zu didn't have to use all sticks.

Unfortunately, Zu didn't solve that problem because it was an algorithm problem rather than a mathematical problem. You can't solve that problem without a computer if there are too many sticks. So please bring your computer and go back to Zu's time to help him so that maybe you can change the history.

There are no more than 10 test cases. For each case:

The first line is an integer N(3 <= N<= 12), indicating the number of sticks Zu Chongzhi had got. The second line contains N integers, meaning the length of N sticks. The length of a stick is no more than 100. The input ends with N = 0.

For each test case, output the maximum total area of triangles Zu could make. Round the result to 2 digits after decimal point. If Zu couldn't make any triangle, print 0.00 .

2014ACM/ICPC亚洲区广州站-重现赛（感谢华工和北大） 

思路：

题意就是问你用n个棍能组成的所有的三角形的面积之和的最大值。一开始的想法是DFS搜索，但是后来写着写着发现不太好写。。然后写着写着就乱了。。所以换了另一种思路，就是先才从小到大排序，然后把其中的不能构成三角形的边剔除，也就是这条边比比它小的两条边的和还大，就这样剔除完之后，从后往前每三个组成一个三角形，直至所剩边数小于等于2。这样的算法是贪心的思想，因为肯定是三角形的个数越多面积越大，（个数小的那些三角形一定能在个数多的那些三角形中用到），然后如果一个边和另外两个边的差值越大，那么它对面积的影响就越小，所以，肯定是相邻的三个最大的边组成的三角形面积最大。

代码：

//AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int a[20];

bool alright(int a,int b,int c)
{
    return b+c>a;
}

double area(double a,double b,double c)
{
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF,n) {
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        double ans=0;
        for (int i=n;i;) {
            if (i<=2) break;
            if (alright(a[i],a[i-1],a[i-2])) {
                ans+=area(a[i],a[i-1],a[i-2]);
                i-=3;
            } else {
                i--;
            }
        }
        printf("%.2f\n",ans);
    }
    return 0;
}