HullMarathon

Time limit8sMemory limit512 MB

Summary

Given N speeds, each rabbit runs up to r_i in any direction for one minute; maximize the convex hull area of the final positions.

Level: Medium6 of 10
Topics: Geometry, Greedy, Brute force, Math
Solved: No attempts yet

Problem

A rabbit likes a sport called full marathon. This sport is played by teams. The members of a team gather at the origin before the race starts. They start running the moment the race starts and stop after 1 minute. The team whose members' positions have the largest convex hull area wins.

You are the coach of a team of $N$ rabbits. The $i$ -th rabbit can travel $r\_i$ in 1 minute. Find the maximum possible area of the convex hull after 1 minute when this team uses an optimal strategy.

Input

The input is given in the following format:

$N$

$r\_1$

...

$r\_N$

Output

Output a real number representing the maximum area of the convex hull on one line. You may print any number of digits after the decimal point, but the answer is accepted when the absolute or relative error is at most $10^{-6}$ .

Constraints

$N$ is between 3 and 8, inclusive.
$r\_i$ is an integer between 1 and 1,000, inclusive.

Examples2

Example 1
Input
```
4
5
8
58
85
```
Expected output
```
2970.000000000
```
Example 2
Input
```
6
1
1
1
1
1
1
```
Expected output
```
2.598076211
```