LeetCode 963. 最小面积矩形 II

文章目录

1. 题目

给定在 xy 平面上的一组点,确定由这些点组成的任何矩形的最小面积,其中矩形的边不一定平行于 x 轴和 y 轴。

如果没有任何矩形,就返回 0。

示例 1:
LeetCode 963. 最小面积矩形 II

输入:[[1,2],[2,1],[1,0],[0,1]]
输出:2.00000
解释:最小面积的矩形出现在 [1,2],[2,1],[1,0],[0,1] 处,面积为 2。

示例 2:
输入:[[0,1],[2,1],[1,1],[1,0],[2,0]]
输出:1.00000
解释:最小面积的矩形出现在 [1,0],[1,1],[2,1],[2,0] 处,面积为 1。

示例 3:
输入:[[0,3],[1,2],[3,1],[1,3],[2,1]]
输出:0
解释:没法从这些点中组成任何矩形。

示例 4:
输入:[[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
输出:2.00000
解释:最小面积的矩形出现在 [2,1],[2,3],[3,3],[3,1] 处,面积为 2。
 
提示:
1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
与真实值误差不超过 10^-5 的答案将视为正确结果。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-area-rectangle-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 直接暴力三重循环+set查找第四点可以做,耗时 104 ms 9.6 MB C++

  • 下面按对角线长度,中点分组,组内的点对才可以组成矩形

class point{
public:
	int x, y;
	point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
    bool operator<(point a) const
    {
        return (x==a.x && y < a.y) || (x < a.x);
    }
};
class Solution {
public:
    double minAreaFreeRect(vector<vector<int>>& points) {
    	map<int,map<point,vector<point>>> m;// square len, midpoint, point
    	int n = points.size(), x1,x2,y1,y2,x3,y3,d;
    	int midx, midy;
    	for(int i = 0; i < n; ++i)
    	{
    		for(int j = i+1; j < n; ++j)
    		{
    			x1 = points[i][0];
    			y1 = points[i][1];
    			x2 = points[j][0];
    			y2 = points[j][1];
    			midx = (x1+x2);//不除以2
    			midy = (y1+y2);
    			d = dis(x1,y1,x2,y2);
    			m[d][point(midx, midy)].push_back(point(x1,y1));
    		}
    	}
    	double area = INT_MAX;
    	int dx1,dy1,dx2,dy2;
    	for(auto it = m.begin(); it != m.end(); ++it)
    	{
    		for(auto it1 = it->second.begin(); it1 != it->second.end(); ++it1)
    		{
    			midx = it1->first.x;
    			midy = it1->first.y;
    			for(int i = 0; i < it1->second.size(); ++i)
    			{
    				x1 = it1->second[i].x;
    				y1 = it1->second[i].y;
    				x2 = midx-x1;
    				y2 = midy-y1;
    				for(int j = i+1; j < it1->second.size(); ++j)
    				{
    					x3 = it1->second[j].x;
    					y3 = it1->second[j].y;
    					dx1 = x1-x3, dy1 = y1-y3;
    					dx2 = x2-x3, dy2 = y2-y3;
    					if(dx1*dx2+dy1*dy2==0)
    					{
    						area = min(area, sqrt(dx1*dx1+dy1*dy1)*sqrt(dx2*dx2+dy2*dy2));
    					}
    				}
    			}
    		}
    	}
    	return area == INT_MAX ? 0 : area;
    }
    int dis(int x1, int y1, int x2, int y2)
    {
    	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }
};

52 ms 21.6 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
LeetCode 963. 最小面积矩形 II

上一篇:删除排序数组中的重复项


下一篇:[SDOI2016] 生成魔咒 - 后缀数组,平衡树,STL,时间倒流