# 939. Minimum Area Rectangle 最小面积矩形

@TOC

## # 题目描述

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. `1 <= points.length <= 500`
2. `0 <= points[i][0] <= 40000`
3. `0 <= points[i][1] <= 40000`
4. All points are distinct.

## # 解题方法

### # 确定对角线，找另外两点（4sum）

Python代码如下：

``````class Solution(object):
def minAreaRect(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
points = map(tuple, points)
points.sort()
pset = set(points)
N = len(points)
res = float('inf')
for i in range(N - 1):
p1 = points[i]
for j in range(i + 1, N):
p4 = points[j]
if p4[0] == p1[0] or p4[1] == p1[1]:
continue
p2 = (p1[0], p4[1])
p3 = (p4[0], p1[1])
if p2 in pset and p3 in pset:
res = min(res, abs(p3[0] - p1[0]) * abs(p2[1] - p1[1]))
return res if res != float("inf") else 0
``````

C++代码如下：

``````class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
set<pair<int, int>> pset;
const int N = points.size();
for (auto p : points) {
pset.insert(make_pair(p[0], p[1]));
}
int res = INT_MAX;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
auto p1 = points[i];
auto p2 = points[j];
if (p1[0] == p2[0] || p1[1] == p2[1])
continue;
pair<int, int> p3 = {p1[0], p2[1]};
pair<int, int> p4 = {p2[0], p1[1]};
if (pset.count(p3) && pset.count(p4))
res = min(res, abs((p2[1] - p1[1]) * (p2[0] - p1[0])));
}
}
return res == INT_MAX ? 0 : res;
}
};
``````

``````class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
set<int> pset;
const int N = points.size();
for (auto p : points) {
pset.insert(40000 * p[0] + p[1]);
}
int res = INT_MAX;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
auto p1 = points[i];
auto p2 = points[j];
if (p1[0] == p2[0] || p1[1] == p2[1])
continue;
vector<int> p3 = {p1[0], p2[1]};
vector<int> p4 = {p2[0], p1[1]};
if (pset.count(40000 * p3[0] + p3[1]) && pset.count(40000 * p4[0] + p4[1]))
res = min(res, abs((p2[1] - p1[1]) * (p2[0] - p1[0])));
}
}
return res == INT_MAX ? 0 : res;
}
};
``````

### # 字典保存出现的x值,y值的点

``````class Solution(object):
def minAreaRect(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
points = map(tuple, points)
points.sort()
xdict, ydict = collections.defaultdict(list), collections.defaultdict(list)
pset = set()
res = float("inf")
for point in points:
xdict[point[0]].append(point)
ydict[point[1]].append(point)
for x1 in xdict.keys():
if len(xdict[x1]) == 1:
continue
for i in range(len(xdict[x1]) - 1):
p1 = xdict[x1][i]
for j in range(i + 1, len(xdict[x1])):
p2 = xdict[x1][j]
for p3 in ydict[p1[1]]:
if p3 != p1:
if (p3[0], p2[1]) in pset:
res = min(res, abs((p3[0] - p1[0]) * (p2[1] - p1[1])))
return res if res != float("inf") else 0
``````

## # 日期

2018 年 11 月 11 日 —— 剁手节快乐