На плоскости задано множество точек с целочисленными координатами.
Необходимо найти минимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при
этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.
Пример входных данных:
3
6 0
0 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных:
24
Очевидно, что вершины невырожденного треугольника должны лежать на разных осях, их координаты должны иметь вид (x, 0) и (0, y). Площадь такого треугольника равна |x| · |y| / 2. Эта площадь будет минимальной при минимально возможных ненулевых значениях |x| и |y|.
Пример правильной программы на Паскале:
program P27;
var
N: integer; {количество точек}
x,y: integer; {координаты очередной точки}
xmin, ymin: integer;
s: real; {площадь}
i: integer;
begin
readln(N);
xmin:=0; ymin:=0;
for i:=1 to N do begin
readln(x,y);
if (x=0) and (y<>0) and
((ymin=0) or (abs(y) < ymin)) then ymin:=abs(y);
if (y=0) and (x<>0) and
((xmin=0) or (abs(x) < xmin)) then xmin:=abs(x);
end;
s:=xmin*ymin/2;
if (s=0) then writeln('Треугольник не существует')
else writeln(s)
end.