[LeetCode]Minimum Area Rectangle

一个矩形可以由任意对角线的两点唯一决定，所以我们只需要用hash set存下所有的点，枚举所有两个对角线的点，看剩下的是不是在set中即可。我们可以把点存成string，但是鉴于输入的范围最多为40000，我们用x * 40001 + y当做key即可。时间复杂度O(N^2)，空间复杂度O(N)，代码如下:

	class Solution {
	public:
	int minAreaRect(vector<vector<int>>& points) {
	unordered_set<long> set;
	for (auto& point : points)
	set.insert(point[0] * 40001 + point[1]);
	int res = 0;
	for (int i = 0; i < points.size(); ++i)
	{
	for (int j = i + 1; j < points.size(); ++j)
	{
	auto point1 = points[i], point2 = points[j];
	if (point1[0] != point2[0] && point1[1] != point2[1])
	{
	if (set.find(point1[0] * 40001 + point2[1]) != set.end() && set.find(point2[0] * 40001 + point1[1]) != set.end())
	{
	int area = abs(point1[0] - point2[0]) * abs(point1[1] - point2[1]);
	res = res? min(res, area): area;
	}
	}
	}
	}
	return res;
	}
	};

view raw Minimum Area Rectangle.cpp hosted with ❤ by GitHub