Определение площади минимального охватывающего прямоугольника

Условие

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

type PointList = Array<[number, number]>;

const computeBoundingBoxArea = (pts: PointList): number => {
    // TODO: реализовать вычисление площади ограничивающего прямоугольника
};

const sample1: PointList = [
    [1, 1],
    [2, 3],
    [5, 5],
];

const sample2: PointList = [
    [-10, -10],
    [23, 13],
    [22, 33],
    [2, 3],
    [50, 50],
];

console.log(computeBoundingBoxArea(sample1)); // 16
console.log(computeBoundingBoxArea(sample2)); // 3600

Ответ

Найдите минимумы и максимумы x и y. Искомая площадь равна (maxX − minX) × (maxY − minY), поскольку стороны прямоугольника обязаны быть параллельны осям.

const computeBoundingBoxArea = (pts: PointList): number => {
  if (!pts.length) return 0;
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  for (const [x, y] of pts) {
    minX = Math.min(minX, x); maxX = Math.max(maxX, x);
    minY = Math.min(minY, y); maxY = Math.max(maxY, y);
  }
  return (maxX - minX) * (maxY - minY);
};

Получаются 16 и 3600. Для пустого набора выбран результат 0; одна точка или точки на одной вертикали/горизонтали также дают нулевую площадь. Предполагаются конечные числовые координаты. Время O(n), память O(1); повёрнутый минимальный прямоугольник — другая задача.