题目地址：https://leetcode.com/problems/minimum-area-rectangle-ii/
题目描述
Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.
Ifthere isn't any rectangle, return 0.
Example 1:
Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.
Example 2:
Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.
Example 3:
Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.
Example 4:
Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.
Note:
1、 1<=points.length<=50；
2、 0<=points[i][0]<=40000；
3、 0<=points[iopeninnewwindow][]<=40000；
4、 Allpointsaredistinct.；
5、 Answerswithin10^-5oftheactualvaluewillbeacceptedascorrect.；
题目大意
给定一组坐标，找出四个顶点使其能构成长方形，求最小的长方形的面积。注意，边有可能不和x,y轴平行。
解题方法
线段长+线段中心+字典
前面有个平行于坐标轴的长方形题目，那个题目是固定对角线的两个点就能找出剩余两个点了，但是这个题可以不和坐标轴平行，那么问题就变大了。。
想来想去还是用长方形的性质，不过很显然仍然是和对象线有关的性质：
1、 长方形的两条对角线长度相等；
2、 长方形的两条对角线互相平分（中点重合）；
注意，如果满足上面两个条件的四边形就是长方形。
用上了这两个性质之后，题目从点的处理直接变成了线段的处理，时间复杂度降到了O(N^2).
具体做法是，我们求出任意两个点构成的线段的长度（的平方）、线段的中心坐标，然后用字典保存成（长度，中心点x，中心点y）：[(线段1起点，线段1终点)， (线段2起点，线段2终点)……]。把这个字典弄好了之后，我们需要对字典做一次遍历，依次遍历相同长度和中心点的两个线段构成的长方形的面积，保留最小值就好了。
知道两条对角线坐标，求长方形的面积，方法是找两条临边，然后相乘即可。
python代码如下：
class Solution(object):
def minAreaFreeRect(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
N = len(points)
(l^2, x#, y#) : [(0,1), (1,2)]
d = collections.defaultdict(list)
for i in range(N - 1):
pi = points[i]
for j in range(i + 1, N):
pj = points[j]
l = (pi[0] - pj[0]) ** 2 + (pi[1] - pj[1]) ** 2
x = (pi[0] + pj[0]) / 2.0
y = (pi[1] + pj[1]) / 2.0
d[(l, x, y)].append((i, j))
res = float("inf")
for l in d.values():
M = len(l)
for i in range(M - 1):
p0, p2 = points[l[i][0]], points[l[i][1]]
for j in range(i + 1, M):
p1, p3 = points[l[j][0]], points[l[j][1]]
d1 = math.sqrt((p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2)
d2 = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
area = d1 * d2
res = min(res, area)
return 0 if res == float('inf') else res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发