{"id":4544,"date":"2018-12-26T21:40:35","date_gmt":"2018-12-27T05:40:35","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4544"},"modified":"2018-12-26T21:43:33","modified_gmt":"2018-12-27T05:43:33","slug":"leetcode-963-minimum-area-rectangle-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-963-minimum-area-rectangle-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 963. Minimum Area Rectangle II"},"content":{"rendered":"\n

Given a set of points in the xy-plane, determine the minimum area of any<\/strong> rectangle formed from these points, with sides not necessarily parallel<\/strong> to the x and y axes.<\/p>\n\n\n\n

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

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

\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>[[1,2],[2,1],[1,0],[0,1]]\nOutput: <\/strong>2.00000\nExplanation:<\/strong> The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>[[0,1],[2,1],[1,1],[1,0],[2,0]]\nOutput: <\/strong>1.00000\nExplanation:<\/strong> The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>[[0,3],[1,2],[3,1],[1,3],[2,1]]\nOutput: <\/strong>0\nExplanation:<\/strong> There is no possible rectangle to form from these points.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]\nOutput: <\/strong>2.00000\nExplanation:<\/strong> The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= points.length <= 50<\/code><\/li>
  2. 0 <= points[i][0] <= 40000<\/code><\/li>
  3. 0 <= points[i][1] <= 40000<\/code><\/li>
  4. All points are distinct.<\/li>
  5. Answers within 10^-5<\/code> of the actual value will be accepted as correct.<\/li><\/ol>\n\n\n\n
    Solution:\u00a0HashTable<\/strong><\/h1>\n\n\n\n
    Iterate all possible triangles and check the opposite points that creating a quadrilateral. <\/p>\n\n\n\n
    Time complexity: O(n^3)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  double minAreaFreeRect(vector>& points) {\n    constexpr double INF_AREA = 1e100;\n    const auto n = points.size();\n    unordered_set s;\n    for (const auto& p : points)\n      s.insert(p[0] << 16 | p[1]);\n    double min_area = INF_AREA;\n    for (int i = 0; i < n; ++i)\n      for (int j = 0; j < n; ++j) {\n        if (i == j) continue;\n        for (int k = 0; k < n; ++k) {\n          if (i == k || j == k) continue;\n          const auto& p1 = points[i];\n          const auto& p2 = points[j];\n          const auto& p3 = points[k];\n          int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +\n                    (p2[1] - p1[1]) * (p3[1] - p1[1]);\n          if (dot != 0) continue;\n          int p4_x = p2[0] + p3[0] - p1[0];\n          int p4_y = p2[1] + p3[1] - p1[1];\n          if (!s.count(p4_x << 16 | p4_y)) continue;\n          double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);\n          double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);\n          double area = a * b;\n          min_area = min(min_area, area);\n        }\n      }\n    return min_area < INF_AREA ? sqrt(min_area) : 0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y…<\/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,177,343],"class_list":["post-4544","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-hashtable","tag-medium","tag-rectangle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4544","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=4544"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4544\/revisions"}],"predecessor-version":[{"id":4546,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4544\/revisions\/4546"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}