Напишите функцию, которая возвращает минимальную площадь среди всех прямоугольников, которые можно построить, используя точки входного массива.

Каждая точка может быть нанесена на график x,y, поэтому, чтобы найти прямоугольник, используя эти точки в методе грубой силы, нам, возможно, придется попробовать все комбинации, таким образом, O(n⁴) Временная сложность, вместо этого с дополнительным пространством и особым свойством мы могли бы найти все прямоугольники за O(n²) Время и O(n) Пространство.

Мы могли бы использовать свойство прямоугольника, т. е. диагонали в прямоугольнике будут иметь перевернутые точки, если одна из диагоналей [[1,2],[4,5]], другая диагональ будет [[1,5],[4,2]], поэтому мы перебираем каждые две пары и смотрим, существуют ли перевернутые точки в входные точки, если это правда, мы нашли прямоугольник.

Одна важная проверка, которую мы должны сделать, заключается в том, что диагональные значения не должны быть равны, [[1,2], [1,3] ] не является диагональю.

Чтобы проверить, существует ли точка в нашем входном массиве, мы могли бы использовать Set со всеми входными точками, таким образом O(1) поиск.

После нахождения прямоугольника вычисление разницы между точками даст нам площадь.

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

Код доступен здесь.

Мы конвертируем точки в строку, [1,2] будет равно "1,2", поэтому мы можем использовать ее как ключ, чтобы проверить, существует ли она.

На каждой итерации у нас есть две точки, мы проверяем, все ли значения в точках не совпадают, затем мы проверяем, находится ли перевернутая диагональ в наборе, если True, мы вычислить площадь (длина * ширина) и обновить минимум.

Наконец, если минимальное значение не изменилось по сравнению с начальным значением, то мы не нашли никаких прямоугольников в точках, поэтому мы возвращаем ноль, иначе минимальное значение.

Сложность по времени составляет O(n²), так как мы используем вложенный цикл for для поиска всех диагоналей.

Сложность пространства составляет O(n), так как мы используем набор для хранения n входных точек.