Задача: 939. Minimum Area Rectangle
Сложность: medium

Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.

Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

👨‍💻 Алгоритм:

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

2⃣Пройти через все пары точек:
Если две точки могут образовать диагональ прямоугольника, то проверить, существуют ли оставшиеся две точки для замкнутого прямоугольника.
Если да, вычислить площадь прямоугольника и обновить минимальную площадь.

3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь.

😎 Решение:

class Solution {
    func minAreaRect(_ points: [[Int]]) -> Int {
        var pointSet = Set(points.map { "\($0[0]),\($0[1])" })
        var minArea = Int.max
        
        for i in 0..<points.count {
            for j in i+1..<points.count {
                let x1 = points[i][0], y1 = points[i][1]
                let x2 = points[j][0], y2 = points[j][1]
                if x1 != x2 && y1 != y2 && pointSet.contains("\(x1),\(y2)") && pointSet.contains("\(x2),\(y1)") {
                    minArea = min(minArea, abs(x2 - x1) * abs(y2 - y1))
                }
            }
        }
        
        return minArea == Int.max ? 0 : minArea
    }
}

Ставь 👍 и забирай 📚 Базу знаний