939. Minimum Area Rectangle

方法1: hash + diagonal Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4 Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] Output: 2

Note:

1 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000All points are distinct.

方法1: hash + diagonal

官方题解：https://leetcode.com/problems/minimum-area-rectangle/solution/ huahua: https://zxi.mytechroad.com/blog/geometry/leetcode-939-minimum-area-rectangle/

思路：

遍历第一次为每个点都建立起hash实现每个点都能在O(1)时间内查找。然后用O(n^2)时间遍历pair，对所有能够形成diagonal的点，查找反对角线的两个点是否都存在。

class Solution { public: int minAreaRect(vector<vector<int>>& points) { if (points.size() < 4) return 0; unordered_map<int, unordered_set<int>> hash; for (auto p: points) hash[p[0]].insert(p[1]); int result = INT_MAX; for (int i = 0; i < points.size(); i++) { for (int j = i + 1; j < points.size(); j++) { int p1x = points[i][0]; int p1y = points[i][1]; int p2x = points[j][0]; int p2y = points[j][1]; if (p1x == p2x || p1y == p2y) continue; if (!hash[p1x].count(p2y) || !hash[p2x].count(p1y)) continue; result = min(result, abs(p2y - p1y) * abs(p1x - p2x)); } } return result == INT_MAX ? 0 : result; } };