Необходимо найти минимально возможную площадь невырожденного (то есть
Условие
На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (то есть имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на биссектрисах углов, образованных осями координат, и при этом ринадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайта. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данныеВ первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.
Пример входных данных:36 6-8 89 7Выходные данныеЕсли искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует». Пример выходных данных для приведённого выше примера входных данных: 48
Формат задания
Решение по шагам
Как рассуждать
Решение. Биссектрисами углов, образованных осями координат, служат две прямые: и Очевидно, что вершины невырожденного треугольника должны лежать на разных биссектрисах, их координаты должны иметь вид (a, a) и (b, -b). Площадь такого треугольника равна |a| · |b|. Эта площадь будет минимальной при минимально возможных ненулевых значениях |a| и |b|. Пример правильной программы на Паскале 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. Пример правильной, но неэффективной программы на языке Паскаль.var points: array[1..10000, 1..2] of integer; {исходные данные} N: integer; {количество точек} mins: integer; {минимальная площадь} a, b: integer; i, j: integer;begin readln(N); mins := MaxInt; 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] <>
Осталось ещё 3 шага
then a := abs(points[i, 1]); if (points[j, 1]…
then b := abs(points[j, 1]); if (a*b < mins)…
then mins := a*b; end; if mins = MaxInt then…
Бесплатно · займёт минуту