Problem E
Sheep Pen
David and Martin retired from their jobs and became shepherds. After each winter they need to rebuild the sheep pen. Each year they have a different collection of straight fence segments of various lengths. Naturally, they want to build a sheep pen that covers the largest area. They always spend a lot of time choosing, rearranging, and placing the segments but they are never sure whether they got the optimal solution. Please help them.
Input
The only input line starts with $n$, the number of fence segments and then contains a list of $n$ integers, the lengths (in meters) of the fence segments. The lengths are integers between $1$ and $100$. The number of fence segments $n$ is between $3$ and $80$.
Output
The output contains one line with the maximum area (in square meters) of a polygon whose sides have lengths given by the input. Not all segment lengths listed need to be used. Answers with an absolute error of at most $0.005$ will be accepted. If no sheep pen can be built, output $0$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 1 1 1 |
1.0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 1 1 |
0.433 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1 1 2 2 7 |
2.0 |
