Problem: Example

Input

4
5
8
58
85


Output

2970.000000000

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e12;
const double PI = acos(-1);
#define EQ(n,m) (abs((n)-(m)) < EPS)

int main(){
    int n;
    cin >> n;
    vector<double> r(n);
    for(int i=0; i<n; i++){
        cin >> r[i];
    }
    sort(r.begin(), r.end());
    
    double ans = 0;
    for(int cn=3; cn<=n; cn++){
        vector<bool> choose(n, false);
        for(int i=0; i<cn; i++){
            choose[n-i-1] = true;
        }
        do{
            vector<double> cr;
            for(int i=0; i<n; i++){
                if(choose[i]){
                    cr.push_back(r[i]);
                }
            }
            do{
                double maxratio = 1;
                for(int i=0; i<cn; i++){
                    maxratio = max(maxratio, abs((cr[0]*cr[1])/(cr[i]*cr[(i+1)%cn])));
                }
                double lb = acos(1/maxratio);
                double ub = PI -lb;
                lb += EPS; ub -= EPS;
                int repnum = 100;
                for(int rep=0; rep<repnum; rep++){
                    double mid = (lb +ub)/2;
                    double cosm = cos(mid);
                    double theta[8];
                    theta[0] = mid;
                    for(int i=1; i<cn; i++){
                        theta[i] = acos((cr[0]*cr[1]) /(cr[i]*cr[(i+1)%cn]) *cosm);
                    }
                    double sum = 0;
                    for(int i=0; i<cn; i++){
                        sum += theta[i];
                    }
                    
                    if(sum > 2*PI){
                        ub = mid;
                    }else{
                        lb = mid;
                    }
                    if(rep == repnum-1 && EQ(2*PI, sum)){
                        double area = 0;
                        for(int i=0; i<cn; i++){
                            area += cr[i] *cr[(i+1)%cn] *sin(theta[i]);
                        }
                        area /= 2.0;
                        ans = max(ans, area);
                    }
                }
          
            }while(next_permutation(cr.begin()+1, cr.end()));
        }while(next_permutation(choose.begin(), choose.end()));
    }

    cout << fixed << setprecision(10);
    cout << ans << endl;
    return 0;
}