{"id":4297,"date":"2018-11-11T15:49:06","date_gmt":"2018-11-11T23:49:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4297"},"modified":"2018-11-13T00:23:00","modified_gmt":"2018-11-13T08:23:00","slug":"leetcode-939-minimum-area-rectangle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-939-minimum-area-rectangle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 939. Minimum Area Rectangle"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

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.<\/p>\n

If there isn’t any rectangle, return 0.<\/p>\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>[[1,1],[1,3],[3,1],[3,3],[2,2]]<\/span>\r\nOutput: <\/strong>4<\/span>\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]<\/span>\r\nOutput: <\/strong>2<\/span>\r\n<\/pre>\n
Note<\/strong>:<\/p>\n
    \n
  1. 1 <= points.length <= 500<\/code><\/li>\n
  2. 0 <=\u00a0points[i][0] <=\u00a040000<\/code><\/li>\n
  3. 0 <=\u00a0points[i][1] <=\u00a040000<\/code><\/li>\n
  4. All points are distinct.<\/li>\n<\/ol>\n
    Solution 1: HashTable + Brute Force<\/h1>\n
    Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.<\/p>\n
    Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)<\/p>\n
    Time complexity: O(n^2)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, running time: 96 ms\r\nclass Solution {\r\npublic:\r\n  int minAreaRect(vector<vector<int>>& points) {    \r\n    unordered_map<int, unordered_set<int>> s;\r\n    for (const auto& point : points)\r\n      s[point[0]].insert(point[1]);\r\n    \r\n    const int n = points.size();\r\n    int min_area = INT_MAX;\r\n    for (int i = 0; i < n; ++i)\r\n      for (int j = i + 1; j < n; ++j) {\r\n        int x0 = points[i][0];\r\n        int y0 = points[i][1];\r\n        int x1 = points[j][0];\r\n        int y1 = points[j][1];\r\n        if (x0 == x1 || y0 == y1) continue;\r\n        int area = abs(x0 - x1) * abs(y0 - y1);\r\n        if (area > min_area) continue;\r\n        if (!s[x1].count(y0) || !s[x0].count(y1)) continue;\r\n        min_area = area;\r\n      }\r\n    return min_area == INT_MAX ? 0 : min_area;\r\n  }\r\n};<\/pre>\n\n<\/div>
    C++ \/ 1D hashtable<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 68 ms\r\nclass Solution {\r\npublic:\r\n  int minAreaRect(vector<vector<int>>& points) {    \r\n    unordered_set<int> s;\r\n    for (const auto& point : points)\r\n      s.insert((point[0] << 16) | point[1]);\r\n    \r\n    const int n = points.size();\r\n    int min_area = INT_MAX;\r\n    for (int i = 0; i < n; ++i)\r\n      for (int j = i + 1; j < n; ++j) {\r\n        int x0 = points[i][0];\r\n        int y0 = points[i][1];\r\n        int x1 = points[j][0];\r\n        int y1 = points[j][1];\r\n        if (x0 == x1 || y0 == y1) continue;\r\n        int area = abs(x0 - x1) * abs(y0 - y1);\r\n        if (area > min_area) continue;\r\n        int p0 = (x1 << 16) | y0;\r\n        int p1 = (x0 << 16) | y1;\r\n        if (!s.count(p0) || !s.count(p1)) continue;\r\n        min_area = area;\r\n      }\r\n    return min_area == INT_MAX ? 0 : min_area;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,82,31,343],"class_list":["post-4297","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-hashtable","tag-math","tag-rectangle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4297","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4297"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4297\/revisions"}],"predecessor-version":[{"id":4306,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4297\/revisions\/4306"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4297"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4297"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4297"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}