На плоскости задано множество точек с целочисленными координатами. Необходимо найти максимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных: 48.
Биссектрисами углов, образованных осями координат, служат две прямые: 
и 
Очевидно, что вершины невырожденного треугольника должны лежать на разных биссектрисах, их координаты должны иметь вид (a, a) и (b, –b). Площадь такого треугольника равна |a| · |b|. Эта площадь будет максимальной при максимальных значениях |a| и |b|.
Пример правильной программы на Паскале
program P27;
var
N: integer; {количество точек}
x,y: integer; {координаты очередной точки}
amax, bmax: integer;
s: integer; {площадь}
i: integer;
begin
readln(N);
amax:=0; bmax:=0;
for i:=1 to N do begin
readln(x,y);
if (x=y) and (abs(x)>amax) then amax:=abs(x);
if (x=-y) and (abs(x)>bmax) then bmax:=abs(x);
end;
s:=amax*bmax;
if s=0 then writeln('Треугольник не существует')
else writeln(s)
end.
Пример правильной, но неэффективной программы на языке Паскаль.
varpoints: array[1..10000, 1..2] of integer; {исходные данные}
N: integer; {количество точек}
maxs: integer; {максимальная площадь}
a, b: integer;
i, j: integer;
begin
readln(N);
maxs := 0;
a := 0; b := 0;
for i := 1 to N do read(points[i, 1], points[i, 2]);
for i := 1 to N do
for j := 1 to N do begin
if (points[i, 1] = points[i, 2]) and (points[i, 1] <> 0) then a := abs(points[i, 1]);
if (points[j, 1] = -points[j, 2]) and (points[j, 1] <> 0) then b := abs(points[j, 1]);
if (a*b>maxs) and (a * b <> 0) then maxs := a*b;
end;
if maxs = 0 then writeln('Треугольник не существует')
else writeln(maxs);
end.