939. Minimum Area Rectangle

https://leetcode.com/problems/minimum-area-rectangle/

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4 Example 2:

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

Note:

1 <= points.length <= 500 0 <= points[i][0] <= 40000 0 <= points[i][1] <= 40000 All points are distinct.

给二维笛卡尔坐标系上一系列点，问能组成的最大的长方形面积是多大。把所有点放到hash map中，后再对每个点检查其余点是否能和它一起组成长方形，也就是遍历其余点并把它当作对角线的点，最后从map中查找是否有剩余的两个点，有就计算面积。

/*
 * @lc app=leetcode id=939 lang=cpp
 *
 * [939] Minimum Area Rectangle
 */

// @lc code=start
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_map<int, unordered_set<int>> m;
        int res = INT_MAX;
        for (const auto &p : points) {
            m[p[0]].insert(p[1]);
        }  
        for (int i = 0; i < points.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (points[i][0] == points[j][0] || points[i][1] == points[j][1]) continue;
                const int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                if (!m[x1].count(y2) || !m[x2].count(y1)) continue;
                res = min(res, abs(x1 - x2) * abs(y1 - y2));
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};
// @lc code=end