939. Minimum Area Rectangle

O(nx * nx * ny) time O(nx * ny) space
当nx趋近于n时时间复杂度上界是O(n²)所以理论上更优
把所有点按序存起来，先按x轴枚举任意两列，再对这两列依次比较相邻两行，找到最小矩形即可

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        map<int, set<int>> m; // 排序+去重
        for (const auto &p : points) {
            m[p[0]].insert(p[1]);
        }
        int res = INT_MAX;
        for (auto i = begin(m); i != end(m); ++i) {
            auto &&si = i->second;
            if (si.size() == 1) continue;
            for (auto j = next(i); j != end(m); ++j) {
                auto &&sj = j->second;
                if (sj.size() == 1) continue;
                bool found_one = false;
                int prev = -1;
                for (int y : sj) {
                    if (!si.count(y)) continue;
                    if (prev > -1) {
                        res = min(res, (j->first - i->first) * (y - prev));
                    }
                    prev = y;
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

O(n²) time O(n) space
用对角线上两点找符合要求的矩形

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<int> s;
        for (const auto &p : points) {
            s.insert(p[0] * 40001 + p[1]); // 把所有点用int来表示
        }
        int res = INT_MAX;
        int n = points.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (points[i][0] == points[j][0] || points[i][1] == points[j][1]) continue;
                if (s.count(points[i][0] * 40001 + points[j][1]) && s.count(points[j][0] * 40001 + points[i][1])) { // 如果对角线两个点能找到对应的组成矩形的反对角线的另外两个点
                    res = min(res, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
                }
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        auto cmp = [](const vector<int> &a, const vector<int> &b){
            return a[0] < b[0] || a[0] == b[0] && a[1] < b[1];
        };
        sort(begin(points), end(points), cmp);
        vector<int> xs;
        unordered_map<int, vector<int>> m;
        for (const auto &p : points) {
            m[p[0]].push_back(p[1]);
            if (xs.empty() || xs.back() != p[0]) {
                xs.push_back(p[0]);
            }
        }
        int res = INT_MAX;
        int nx = xs.size();
        for (int i = 0; i < nx; ++i) {
            if (m[xs[i]].size() == 1) continue;
            for (int j = i + 1; j < nx; ++j) {
                if (m[xs[j]].size() == 1) continue;
                res = min(res, helper(m, xs[i], xs[j]));
            }
        }
        return res == INT_MAX ? 0 : res;
    }

    int helper(unordered_map<int, vector<int>> &m, int a, int b) {
        unordered_set<int> s(begin(m[a]), end(m[a]));
        int n = m[b].size();
        int diff = INT_MAX;
        for (int i = 0; i < n; ++i) {
            if (!s.count(m[b][i])) continue;
            int j = i + 1;
            while (j < n && !s.count(m[b][j])) ++j;
            if (j == n) break;
            diff = min(diff, m[b][j] - m[b][i]);
            i = j - 1;
        }
        return diff == INT_MAX ? diff : (b - a) * diff;
    }
};