На плоскости задано множество точек с целочисленными координатами.
Необходимо найти минимально возможную площадь невырожденного (т. е.
имеющего ненулевую площадь) треугольника, одна вершина которого
расположена в начале координат, а две другие лежат на биссектрисах углов,
образованных осями координат, и при этом принадлежат заданному
множеству. Если такого треугольника не существует, необходимо вывести
соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу
для решения этой задачи.
Программа считается эффективной по времени, если при увеличении
количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для
хранения всех необходимых данных не зависит от количества точек и не
превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите
язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа – координаты
очередной точки.
Пример входных данных:
3
6 6
-8 8
9 7
Выходные данные
Если искомый треугольник существует, программа должна напечатать одно
число: минимально возможную площадь треугольника, удовлетворяющего
условиям. Если искомый треугольник не существует, программа должна
напечатать сообщение: «Треугольник не существует».
Пример выходных данных для приведённого выше примера входных данных:
48

Ответить

Полный код: (Почему то не прошел весь) :)
program P27;
var
N: integer; {количество точек}
x,y: integer; {координаты очередной точки}
amin, bmin: integer;
s: integer; {площадь}
i: integer;
begin
readln(N);
amin:=0; bmin:=0;
for i:=1 to N do begin
readln(x,y);
if (x=y) and (x<>0) and
((amin=0) or (abs(x)<amin)) then amin:=abs(x);
if (x=-y) and (x<>0) and
((bmin=0) or (abs(x)<bmin)) then bmin:=abs(x);
end;
s:=amin*bmin;
if s=0 then writeln('Треугольник не существует')
else writeln(s)
end.

Ответить

Мельком глянул, вроде всё верно. По критериям оценки программа эффективная. Не знаю, к чему придрались.

Ответить