题目如下：
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: 4Example 2:
Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] Output: 2Note:
1 <= points.length <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000- All points are distinct.
解题思路：题目中约定了矩形的各边要与X轴或者Y轴平行，所以不妨把所有的点按X轴进行分组。例如 [[1,1],[1,3],[3,1],[3,3],[2,2]]，以X的坐标分组后得到 {1: [1, 3], 2: [2], 3: [1, 3]}，接下来只要判断两个不同的X轴所对应的Y轴的list中是否存在相同的元素，如果相同则表示可以组成一个题目中要求的矩形。最后求出最小面积即可。
代码如下：
class Solution(object): def minAreaRect(self, points): """ :type points: List[List[int]] :rtype: int """ dic_x = {} res = float(‘inf‘) x_set = set() for (x,y) in points: dic_x[x] = dic_x.setdefault(x,[]) + [y] x_set.add(x) x_list = sorted(list(x_set)) for kx1 in range(len(x_list)): for kx2 in range(kx1+1,len(x_list)): intersection = sorted((list(set(dic_x[x_list[kx1]]) & set(dic_x[x_list[kx2]])))) if len(intersection) < 2: continue minDis = intersection[-1] - intersection[0] for i in range(len(intersection)-1): minDis = min(minDis,intersection[i+1] - intersection[i]) #print kx1,kx2,intersection res = min(res, minDis * abs(x_list[kx1]-x_list[kx2])) return res if res != float(‘inf‘) else 0
【leetcode】939. Minimum Area Rectangle
原文：https://www.cnblogs.com/seyjs/p/10168101.html