Необходимо найти максимально возможную площадь невырожденного (то есть
Условие
На плоскости задано множество точек с целочисленными координатами. Необходимо найти максимально возможную площадь невырожденного (то есть, имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение. Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данныеВ первой строке задаётся N - количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа - координаты очередной точки.
Пример входных данных:36 00 89 7Выходные данныеЕсли искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует». Пример выходных данных для приведённого выше примера входных данных:24
Формат задания
Решение по шагам
Как рассуждать
Решение. Очевидно, что вершины невырожденного треугольника должны лежать на разных осях, их координаты должны иметь вид (x,
Осталось ещё 7 шагов
и (0, y). Площадь такого треугольника равна…
Эта площадь будет максимальной при…
and (points[i, 2] <>…
then a := abs(points[i, 2]); if (points[j, 1]…
and (points[j, 2] =…
then b := abs(points[j, 1]); if (a*b>maxs)…
then maxs := a*b/2; end; if maxs = 0 then…
Бесплатно · займёт минуту