A set of points on a plane
Problem
A set of points with integer coordinates is given on the plane. It is necessary to find a triangle of the largest area with vertices at these points, one of whose sides lies on the OX axis. Write a memory and time efficient program that will solve this problem. The size of the memory that the program uses should not depend on the length of the passed number sequence.
The first line is a single positive integer – number of points N. Each of the following N lines contains two – first the x coordinate, then the y coordinate of the next point.
The program should output a single number – the maximum area of a triangle that satisfies the conditions of the problem. If no such triangle exists, the program should output zero.
Sample input:
6
0 0
2 0
3 3
5 5
-6 -6
1 2
Example output for the example input above:
6