Fence In Godzilla!

Time limit1sMemory limit128 MB

Summary

The task is to find the smallest nonzero area among triangles with vertices from n points.

Level: Hard8 of 10
Topics: Geometry, Sorting, Two pointers
Solved: No attempts yet

Problem

We caught Godzilla! After a long chase we finally managed to trap Godzilla, who had been brazenly chewing through the television cables. The only question left is where to keep the beast.

Someone suggested fencing Godzilla in with a triangular enclosure. Each of the three corners of the fence must stand at a tree growing in the forest. In other words, you pick three of the given trees and use their positions as the vertices of a triangular plot.

To leave as much of the forest as possible, the area of the triangular plot holding Godzilla must be as small as possible. Determine how small this triangular plot can be.

Input

The first line contains the number of trees $n$ ( $3 \le n \le 2000$ ).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ , the coordinates of one tree, separated by a space ( $-10^9 \le x_i, y_i \le 10^9$ ).

No two trees stand at the same point, and not all of the trees lie on a single line.

Output

Among all triangles whose vertices are three of the trees, find the one with the smallest area and print a single integer equal to twice that area.

Degenerate triangles, whose three vertices are collinear and whose area is $0$ , are not considered: you cannot keep Godzilla inside one of those.

Because all coordinates are integers, twice the area is always an integer.

Examples5

Example 1
Input
```
5
-7 4
-7 2
7 -2
-5 5
5 -4
```
Expected output
```
4
```
Example 2
Input
```
3
0 0
1 0
0 1
```
Expected output
```
1
```
Example 3
Input
```
3
0 0
4 0
0 4
```
Expected output
```
16
```
Example 4
Input
```
4
0 0
1 0
2 0
5 7
```
Expected output
```
7
```
Example 5
Input
```
6
0 0
1 0
2 0
3 0
10 0
0 1
```
Expected output
```
1
```