Leetcode 963. 最小面积矩形 II 解题思路及C++实现

解题思路：

这道题目的难点在于如何判断一个矩形，网上也有很多方法。

对于给定的四个点，可以判断其四个顶点是否是直角，或者先求出中心点，矩形中每个点到中心点的距离是相等的。

下面给出的程序的逻辑是：暴力遍历每三个顶点，先判断其是否构成两条垂直的边，如果垂直的话，就去找第四个顶点，通过一个 unordered_set 查找，即可知道points数组中是否存在第四个点。

判断是否垂直：向量内积为0

求第四个点：向量运算

 

class Solution { public:double minAreaFreeRect(vector<vector<int>>& points) {int n = points.size();if(n < 4) return 0;unordered_set<string> h;for(int i = 0; i < points.size(); i++){h.insert(to_string(points[i][0]) + " " + to_string(points[i][1]));}double res = INT_MAX;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){for(int k = j + 1; k < n; k++){update(points[i], points[j], points[k], res, h);update(points[j], points[i], points[k], res, h);update(points[k], points[i], points[j], res, h);}}}if(res == INT_MAX) res = 0;return res;}void update(const vector<int>& x, const vector<int>& y, const vector<int>& z, double& res, const unordered_set<string>& h){int x1 = x[0] - y[0];int y1 = x[1] - y[1];int x2 = x[0] - z[0];int y2 = x[1] - z[1];vector<int> p(2);if(x1*x2 + y1*y2 == 0){p[0] = z[0] - x1;p[1] = z[1] - y1;if(h.find(to_string(p[0]) + " " + to_string(p[1])) != h.end()){res = min(res, sqrt(x1*x1 + y1*y1) * sqrt(x2*x2 + y2*y2));}}} };

 

 

 

总结

以上是生活随笔为你收集整理的Leetcode 963. 最小面积矩形 II 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。