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