Задача.
Дан массив точек на плоскости. Нужно найти минимальную площадь прямоугольника образованного этими точками, у которого стороны параллельны оси x и y.
Если такого прямоугольника нет – в качестве результата вернуть 0.
Например,
Для точек: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Ответ 2.
Ссылка на leetcode: https://leetcode.com/problems/minimum-area-rectangle/
Решение.
Первое решение, которое приходит в голову – это полный перебор. Нам нужно перебрать все наборы из 4 разных точек, проверить, что они образуют прямоугольник с осями, параллельными осям x и y, вычислить площадь и найти минимальную среди них.
Такой перебор можно организовать при помощи 4 вложенных друг в друга циклов, каждый из которых это цикл по всем заданным точкам.
Для произвольных 4 точек: A, B, C, D, условия, что они образуют прямоугольник, параллельный осям x и y:
yA != yB
xB != xC
yB == yC
xC == xD
yD == yA
Если эти 4 точки образуют прямоугольник, параллельный осям x и y, так, как изображено на рисунке, то площадь будет равна:
В коде это выглядит следующим образом:
int minArea = Integer.MAX_VALUE;
for (int pointA[] : points) {
for (int pointB[]: points) {
for (int pointC[] : points) {
for (int pointD[] : points) {
if (pointA[0] == pointB[0]
&& pointA[1] != pointB[1]
&& pointB[1] == pointC[1]
&& pointB[0] != pointC[0]
&& pointD[0] == pointC[0]
&& pointD[1] == pointA[1]
) {
minArea = Math.min(minArea, Math.abs(pointA[1] – pointB[1]) * Math.abs(pointA[0] – pointD[0]));
}
}
}
}
}
return minArea == Integer.MAX_VALUE ? 0 : minArea;
}
Временная сложность O(n^4) из-за 4 вложенных циклов.
Сложность по памяти O(1), т.к. мы не используем никакой дополнительной памяти.
Как можно улучшить это решение?
Можно заметить, что для задания прямоугольника с осями, параллельными осям x и y, достаточно указать всего 2 точки, вместо 4. Для этого достаточно указать координаты точек, лежащих на диагонали, например, A и C. Тогда координаты точек B и D можно вычислить.
Точки A и C образуют диагональ, если их координаты x и y отличаются:
yA != yC
Тогда координаты точек B и D:
xB = xA
yB = yC
D:
xD = xC
yD = yA
Используя этот факт, мы может сократить перебор до 2 вложенных циклов. Мы будем перебирать все пары точек. Для каждой пары точек проверим, образуют ли они диагональ (координаты x и y не равны). Если они образуют диагональ – вычислим координаты точек B и D. Далее нам нужно проверить, если ли точки с такими координатами во входных данных.
Для быстрой проверки нам нужно закешировать все точки в хэш-таблице. В качестве ключа в такой таблице у нас будет “x” кордината точки, а в качестве значения – Set всех “y” координат точек с заданной “x” координатой.
Если точки B и D есть в нашей хэш-таблице, то вычислим его площадь и найдем минимальную площадь.
В коде это выглядит так:
int minArea = Integer.MAX_VALUE;
//Кэшируем все точки
// key – x координата,
//value – множество y координат с фиксированной x координатой
HashMap<Integer, Set<Integer>> map = new HashMap<>();
for (int point[] : points) {
if (!map.containsKey(point[0])) {
map.put(point[0], new HashSet<>());
}
map.get(point[0]).add(point[1]);
}
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
int pointA[] = points[i];
int pointC[] = points[j];
//Если точки A и C образуют диагональ
//И в хэш-таблице есть точки B и D
if (pointA[0] != pointC[0]
&& pointA[1] != pointC[1]
&& map.get(pointA[0]).contains(pointC[1])
&& map.get(pointC[0]).contains(pointA[1])) {
//Вычисляем площадь и находим минимум
minArea = Math.min(minArea, Math.abs(pointA[1] – pointC[1]) * Math.abs(pointA[0] – pointC[0]));
}
}
}
return minArea == Integer.MAX_VALUE ? 0 : minArea;
}
Временная сложность O(n^2).
Сложность по памяти O(n) из-за хранения точек в хэш-таблице.
