939. Minimum Area Rectangle

by

939. Minimum Area Rectangle

Medium

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. 1 <= points.length <= 500
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. All points are distinct.

思路

将所有点放进一个集合。

对所有点进行两两组和，判断它们是否可以是一个矩形的对角点（因为要求是边平行于坐标轴的矩形，因此只需检测横纵坐标是否均不同，且一对对角点可唯一确定一个矩形）。

若可以，则进一步判断该矩形的另两个对角点是否在已有点的集合中。

若在，则计算面积并与之前的最小面积比较更新。

最后返回最小面积。

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        set<pair<int, int>> points_set;
        for (auto point: points) {
            points_set.insert(pair<int, int>(point[0], point[1]));
        }
        
        int min_area = INT_MAX;
        int size = points.size();
        auto points_set_end = points_set.end();
        for (int i = 0; i < size - 1; ++i) {
            for (int j = i + 1; j < size; ++j) {
                if (points[i][0] == points[j][0] || points[i][1] == points[j][1]) continue;
                else {
                    if (points_set.find(pair<int, int>(points[i][0], points[j][1])) != points_set_end && points_set.find(pair<int, int>(points[j][0], points[i][1])) != points_set_end) {
                        int area = abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]);
                        min_area = area < min_area ? area : min_area;
                    }
                }
            }
        }
        min_area = min_area == INT_MAX ? 0 : min_area;
        
        return min_area;
    }
};

Runtime: 436 ms, faster than 65.62% of C++ online submissions for Minimum Area Rectangle.

Memory Usage: 20.9 MB, less than 78.67% of C++ online submissions for Minimum Area Rectangle.

Leave a Comment