A. All-Save Challenge
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After a terrible storm, you receive the locations of $$$n$$$ people waiting to be rescued. To protect them until help arrives, you can create a safety zone in the shape of an equilateral triangle. The safety zone may be placed anywhere and rotated by any angle. A person is protected if their location is inside the triangle or on its boundary.

Since a larger safety zone requires more energy, you want to make it as small as possible. Find the minimum possible area of a safety zone that protects all $$$n$$$ people.

Recall that a triangle is called an equilateral triangle if and only if all its sides have the same length.

Input

The first line contains an integer $$$n$$$.

The $$$i$$$-th line of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, representing the location of the $$$i$$$-th person.

  • $$$1 \leq n \leq 5 \times 10^5$$$
  • $$$-10^9 \leq x_i, y_i \leq 10^9$$$
  • No two people are at the same location.
Output

Output the minimum possible area.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
3
3 0
4 4
0 3
Output
7.79422863405994782087
Input
5
-1 -2
3 1
0 4
4 3
-3 2
Output
34.02164503538821491556
Input
2
-1000000000 -1000000000
1000000000 1000000000
Output
3464101615137754587.05489268301174473389
Note

The following figure shows a minimum-area safety zone for the first sample. The red points represent the locations of the three people.