Largest Triangle
Description
Given a convex polygon, you are required to find the triangle with the largest area among all triangles whose vertices coincide with the vertices of the polygon.
The input consists of no more than $50$ test cases. The first line of each test case contains an integer $n$, representing the number of vertices of the polygon ($3 \le n \le 20,000$). Each of the next $n$ lines contains two integers ranging from $-10^9$ to $10^9$, representing the coordinates of the vertices. It is guaranteed that the given polygon is non-degenerate and strictly convex, meaning it is convex and no three of its vertices lie on the same line. The vertices are enumerated in counterclockwise order. The input is terminated by a line containing a single zero, which should not be processed. The tests are generated with some kind of random.
For each test case, output a single positive integer, which is equal to twice the area of the required triangle. It can be easily proved that these numbers are always integers.
Input
The input consists of no more than $50$ test cases. The first line of each test case contains an integer $n$, representing the number of vertices of the polygon ($3 \le n \le 20,000$). Each of the next $n$ lines contains two integers ranging from $-10^9$ to $10^9$, representing the coordinates of the vertices. It is guaranteed that the given polygon is non-degenerate and strictly convex, meaning it is convex and no three of its vertices lie on the same line. The vertices are enumerated in counterclockwise order. The input is terminated by a line containing a single zero, which should not be processed. The tests are generated with some kind of random.
Output
For each test case, output a single positive integer, which is equal to twice the area of the required triangle. It can be easily proved that these numbers are always integers.
4
-1 -1
1 -1
2 1
0 1
5
0 0
5 0
5 2
2 4
0 2
0
4
20