Area of a non-degenerate triangle - 2
Problem
A set of points with integer coordinates is specified on the plane. It is necessary to find the minimum possible area of a non-degenerate (that is, having a non-zero area) triangle, one of whose vertices is located at the origin, and the other two lie on the bisectors of the angles formed by the coordinate axes, and at the same time belong to a given set. If such a triangle does not exist, print "NO".
Write a time and memory efficient program to solve this problem.
A program is considered efficient in time if, with an increase in the number of points by a factor of k, the running time increases by no more than k times.
A program is considered memory efficient if the size of the memory to store 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, indicate the programming language and its version.
Input
The first line specifies N – the number of points in the given set.
The following lines each contain two integers – coordinates of the next point.
Output
If the required triangle exists, the program should print a single number: the minimum possible area of the triangle that satisfies the conditions. If the required triangle does not exist, the program should print the message: «NO».
Examples
| # |
Input |
Output |
| 1 |
3
6 6
-8 8
9 7
|
48 |