A set of points with integer coordinates is given on the plane. It is necessary to find the maximum possible area of a non-degenerate (that is, having a non-zero area) triangle, one vertex of which is located at the origin of coordinates, and the other two lie on the bisectors of the angles formed by the coordinate axes, and moreover, they belong to the given set. If such a triangle does not exist, an appropriate message should be displayed. Write a time and memory efficient program to solve this problem.
A program is considered efficient in time if the increase in the number of points by k times increases the running time by no more than k times. A program is considered memory efficient if the memory size for storing all the necessary data does not depend on the number of points and does not exceed 1 kilobyte. Before the text of the program, briefly describe the solution algorithm and indicate
programming language and its version.
Input
The first line specifies N – the number of points in the given set. Each of the following lines contains two integers – coordinates of the next point.
Output
If the desired triangle exists, the program should print a single number: the maximum possible area of the triangle that satisfies the conditions. If the required triangle does not exist, the program should print the message: "No solution".
| Input |
Output |
|
3
6 6
-8 8
9 7
|
48 |