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 axes.
If there isn’t any rectangle, return 0.
Example 1:
Input: [[1,2],[2,1],[1,0],[0,1]] Output: 2.00000 Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.
Example 2:
Input: [[0,1],[2,1],[1,1],[1,0],[2,0]] Output: 1.00000 Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.
Example 3:
Input: [[0,3],[1,2],[3,1],[1,3],[2,1]] Output: 0 Explanation: There is no possible rectangle to form from these points.
Example 4:
Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]] Output: 2.00000 Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.
Note:
1 <= points.length <= 500 <= points[i][0] <= 400000 <= points[i][1] <= 40000- All points are distinct.
- Answers within
10^-5of the actual value will be accepted as correct.
Solution: HashTable
Iterate all possible triangles and check the opposite points that creating a quadrilateral.
Time complexity: O(n^3)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public: double minAreaFreeRect(vector<vector<int>>& points) { constexpr double INF_AREA = 1e100; const auto n = points.size(); unordered_set<int> s; for (const auto& p : points) s.insert(p[0] << 16 | p[1]); double min_area = INF_AREA; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (i == j) continue; for (int k = 0; k < n; ++k) { if (i == k || j == k) continue; const auto& p1 = points[i]; const auto& p2 = points[j]; const auto& p3 = points[k]; int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) + (p2[1] - p1[1]) * (p3[1] - p1[1]); if (dot != 0) continue; int p4_x = p2[0] + p3[0] - p1[0]; int p4_y = p2[1] + p3[1] - p1[1]; if (!s.count(p4_x << 16 | p4_y)) continue; double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2); double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2); double area = a * b; min_area = min(min_area, area); } } return min_area < INF_AREA ? sqrt(min_area) : 0; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
hi:
有个地方没看懂，能提示一下吗？
int dot = (p2[0] – p1[0]) * (p3[0] – p1[0]) +
(p2[1] – p1[1]) * (p3[1] – p1[1]);
if (dot != 0) continue;
int p4_x = p2[0] + p3[0] – p1[0];
int p4_y = p2[1] + p3[1] – p1[1];
这段代码是确定三个点是否能组成直角三角形对吗？为什么呢
向量 p1p2 和 向量 p1p3 的点积(dot product)为0的话表示它们垂直，则p1p2p3构成一个直角三角形（不一定等腰）
v1 = (x1, y1) 和 v2 = (x2, y2) 的点积 v1 * v2 = x1 * x2 – y1 * y2
是余弦定理的一个特例 cos(90) = v1 * v2 / (|v1| * | v2|) = 0 => v1 * v2 = 0