Максимизируйте площадь треугольника, образованного точками на сторонах данного прямоугольника

Опубликовано: 20 Сентября, 2022

Дан прямоугольник [(x1, y1), (x2, y2)], обозначающий координаты нижнего левого угла и верхнего правого угла, стороны которого параллельны осям координат и N точек на его периметре (не менее одной на каждой стороне) . Задача состоит в том, чтобы максимизировать площадь треугольника, образованного этими точками.

Примеры:

Input: rectangle[][]= {{0, 0}, {6, 6}}, 
coordinates[][] = {{0, 2}, {0, 3}, {0, 5}, {2, 0}, {3, 0}, {6, 0}, {6, 4}, {1, 6}, {6, 6}}
Output: 18
Explanation: Refer to the image below for explanation. 

Подход: Чтобы найти треугольник максимальной площади по координатам на заданном прямоугольнике, найдите координаты на каждой стороне, которые наиболее удалены друг от друга. Итак, предположим, что есть четыре стороны a, b, c, d, где a и c — длина прямоугольника, а b, d — ширина . Теперь максимальная площадь будет
MAX (длина * (расстояние между самыми дальними координатами по любой из ширин)/2, ширина * (расстояние между самыми дальними координатами по любой из длин)/2).
Выполните следующие шаги, чтобы решить данную проблему.

  • Вычислите длину = абс (x2 – x1) и ширину = абс (y2 – y1)
  • Найдите координаты, которые наиболее удалены друг от друга с каждой стороны.
  • Используйте приведенную выше формулу для расчета площади.
  • Верните найденную область.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N), где N — количество заданных координат.
Вспомогательное пространство: О(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ