Problem A
Ant Attack
Gregor is out in the back yard studying all the insects moving around. In particular, he is inspecting the myriad of ants scattered out on a large flat stone. Gregor wants to collect all the ants to study them in his ant terrarium. Given where all the ants are placed right now, Gregor wants to know what is the smallest box that could capture all the ants he sees right now at the same time. Smallest is measured in the area of the bottom of the rectangular box. He will capture all the ants simulatenously, by placing the box on the stone, and may therefore rotate the box at any angle to minimize the size of the box. The solution to the sample input is illustrated in the figure.
Input
The first line of input contains the number $N$, which is the number of ants on the stone. On the following $N$ lines contain $x_i$ and $y_i$ which is coordinates of the i’th ant in a flat cartesian plane.
It is given that no points coincide, and that the solution area is non-zero.
Output
Output the smallest area of a rectangle that contains all the ants. Ants may be located arbitrarily close to an edge of the box, meaning they can effectively be on the edge of the box. The answer must be accurate to within an absolute and relative error of $10^{-5}$.
Limits
-
$1 \leq N \leq 10^{5}$
-
$-1 \leq x_i, y_i \leq 1$
| Sample Input 1 | Sample Output 1 |
|---|---|
5 -0.2 -0.2 0.2 -0.1 0.0 0.1 0.5 0.2 0.1 0.1 |
0.18823529411764706 |
