# 963. Minimum Area Rectangle II

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. `1 <= points.length <= 50`
2. `0 <= points[i][0] <= 40000`
3. `0 <= points[i][1] <= 40000`
4. All points are distinct.
5. Answers within `10^-5` of the actual value will be accepted as correct.

``````class Solution {
public:
double minAreaFreeRect(vector<vector<int>>& points) {
int n = points.size();
if (n < 4) return 0.0;
double res = DBL_MAX;
unordered_map<string, vector<vector<int>>> m;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
long dist = getLength(points[i], points[j]);
double centerX = (points[i][0] + points[j][0]) / 2.0;
double centerY = (points[i][1] + points[j][1]) / 2.0;
string key = to_string(dist) + "_" + to_string(centerX) + "_" + to_string(centerY);
m[key].push_back({i, j});
}
}
for (auto &a : m) {
vector<vector<int>> vec = a.second;
if (vec.size() < 2) continue;
for (int i = 0; i < vec.size(); ++i) {
for (int j = i + 1; j < vec.size(); ++j) {
int p1 = vec[i][0], p2 = vec[j][0], p3 = vec[j][1];
double len1 = sqrt(getLength(points[p1], points[p2]));
double len2 = sqrt(getLength(points[p1], points[p3]));
res = min(res, len1 * len2);
}
}
}
return res == DBL_MAX ? 0.0 : res;
}
long getLength(vector<int>& pt1, vector<int>& pt2) {
return (pt1[0] - pt2[0]) * (pt1[0] - pt2[0]) + (pt1[1] - pt2[1]) * (pt1[1] - pt2[1]);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/963

Minimum Area Rectangle

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

https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/208361/JAVA-O(n2)-using-Map

https://leetcode.com/problems/minimum-area-rectangle-ii/discuss/210786/C%2B%2B-with-picture-find-diagonals-O(n-*-n)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation