Menu Close

Find the minimum area of a rectangle that can be formed from given points.

Given an array of set of points in the X-Y plane. The task is to find the minimum area of a rectangle that can be formed from these points. The sides of the rectangle should be parallel to the X and Y axes. If a rectangle cannot be formed with the given points then print 0.
Examples:
Input: [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
Output: 4

Input: [[1, 1], [1, 3], [3, 1], [3, 3], [4, 1], [4, 3]]
Output: 2

```import collections
def Area(A):
dict = collections.defaultdict(list)
for x, y in A:
dict[x].append(y)
L = {}
ans = float('inf')
for x in sorted(dict):
column = dict[x]
column.sort()
for j, y2 in enumerate(column):
for i in range(j):
y1 = column[i]
if (y1, y2) in L:
ans = min(ans, (x - L[y1, y2]) * (y2 - y1))
L[y1, y2] = x
if ans < float('inf'):
return ans
else:
return 0

N=int(input('Enter the number of Coordinates : '))
print("Enter the Coordinates : ")
A=[]
for i in range(N):
A.append(list(map(int,input('').split(' '))))
print('The Coordinates are : ',A)
print(Area(A))```

Input_1:
Enter the number of Coordinates : 5
Enter the Coordinates :
1 1
1 3
3 1
3 3
2 2
The Coordinates are : [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
Output:
4

Input_2:
Enter the number of Coordinates : 6
Enter the Coordinates :
1 1
1 3
3 1
3 3
4 1
4 3
The Coordinates are : [[1, 1], [1, 3], [3, 1], [3, 3], [4, 1], [4, 3]]
Output:
2

Sample Output Picture ?

More Q