Triangle on the Axis

Interview

Time limit2sMemory limit2048 MB

Summary

Given integer points in the plane, find the largest-area triangle with one side on the Ox axis, or print 0 if no non-degenerate triangle exists.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Statement

You are given a set of points on a plane with integer coordinates. Find the triangle with the largest area whose vertices all belong to this set and whose one side lies on the $Ox$ axis.

Input

The first line contains an integer $n$ , the number of points ( $1 \le n \le 1000$ ). Each of the following $n$ lines contains two integers $x$ and $y$ , the coordinates of a point. All coordinates are at most $1000$ in absolute value.

Output

Output a single real number, the maximum area of a triangle that satisfies the conditions. If no such triangle exists, or the only triangles are degenerate, output $0$ . Your answer is correct if it differs from the exact value by no more than $10^{-9}$ .

Hint

The picture is shown below.

Examples2

Example 1
Input
```
3
0 0
1 0
2 -3
```
Expected output
```
1.5
```
Example 2
Input
```
3
1 0
2 1
3 3
```
Expected output
```
0
```