OpenKattis
Kattis Set 12

#### Start

2020-04-06 05:15 AKDT

## Kattis Set 12

#### End

2020-04-13 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -440 days 23:45:13

164:15:00

0:00:00

# Problem DLargest Triangle

Given $N$ points on a $2$-dimensional space, determine the area of the largest triangle that can be formed using $3$ of those $N$ points. If there is no triangle that can be formed, the answer is $0$.

## Input

The first line contains an integer $N$ ($3 \le N \le 5\, 000$) denoting the number of points. Each of the next $N$ lines contains two integers $x$ and $y$ ($0 \leq x, y \leq 4 \cdot 10^7$). There are no specific constraints on these $N$ points, i.e. the points are not necessarily distinct, the points are not given in specific order, there may be $3$ or more collinear points, etc.

## Output

Print the answer in one line. Your answer should have an absolute error of at most $10^{-5}$.

Sample Input 1 Sample Output 1
7
0 0
0 5
7 7
0 10
0 0
20 0
10 10

100.00000