数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找给定坐标集的矩形最小面积
假设我们有一个 XY 平面中一些点的数组。我们必须找到可以从这些点形成的矩形的最小面积。矩形的边应平行于 X 和 Y 轴。如果我们无法形成矩形，则返回 0。因此，如果点的数组类似于 [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)]。输出将为 4。因为可以使用点 (1, 1), (1, 3), (3, 1) 和 (3, 3) 形成矩形。
为了解决这个问题，请按 x 坐标给出点，以便将直线上垂直线上的点组合在一起。然后，对于组中每一对点，例如 (x, y1) 和 (x, y2)，我们将找到具有这对点作为要形成的矩形的右边缘的最小矩形。我们可以通过跟踪之前访问过的所有其他点对来做到这一点。最后返回获得的矩形的最小可能面积。
示例
import collections
def findMinArea(Arr):
columns = collections.defaultdict(list)
for x, y in Arr:
columns[x].append(y)
lastx = {}
ans = float('inf')
for x in sorted(columns):
col = columns[x]
col.sort()
for j, y2 in enumerate(col):
for i in range(j):
y1 = col[i]
if (y1, y2) in lastx:
ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
lastx[y1, y2] = x
if ans < float('inf'):
return ans
else:
return 0
A = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
print('Minimum area of rectangle:',findMinArea(A))输出
Minimum area of rectangle: 4
更新于: 2019-12-18
340 次查看
广告