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: 4


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

 
Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Difficulty: MEDIUM
Tags: Geometry

Sorting

Data structures

Mathematics
Skill types: Sorting

Data structures

Starter code:
class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def minAreaRect(self, points):
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y and ((p1x, p2y) in pSet) and ((p2x, p1y) in pSet):
					ans = min(ans, abs((p1x - p2x) * (p1y - p2y)))
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		if len(set(X[0])) == 1 or len(set(X[1])) == 1:
			return 0
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				area = abs((p2x - p1x) * (p2y - p1y))
				if area > ans or area == 0:
					continue
				if (p1x, p2y) in pSet and (p2x, p1y) in pSet:
					ans = area
		return ans if ans < float('inf') else 0
from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		(Nr, Nc) = (len(set(X[0])), len(set(X[1])))
		if Nr == 1 or Nc == 1:
			return 0
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in list(columns.items()):
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						area = (r - lastc[c1, c2]) * (c2 - c1)
						if area < ans:
							ans = area
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0
from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		(Nr, Nc) = (len(set(X[0])), len(set(X[1])))
		if Nr == 1 or Nc == 1:
			return 0
		if Nr < Nc:
			points = [[c, r] for (r, c) in points]
			return self.minAreaRect(points)
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in list(columns.items()):
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						area = (r - lastc[c1, c2]) * (c2 - c1)
						if area < ans:
							ans = area
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0
from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		d = defaultdict(set)
		(rset, cset, N, ans) = (set(), set(), len(points), float('inf'))
		for (r, c) in points:
			rset.add(r)
			cset.add(c)
		(Nr, Nc) = (len(rset), len(cset))
		if Nr == 1 or Nc == 1:
			return 0
		elif Nr < Nc:
			for (r, c) in points:
				d[r].add(c)
		else:
			for (r, c) in points:
				d[c].add(r)
		A = sorted(d.keys())
		for (i, r1) in enumerate(A):
			cols1 = d[r1]
			for r2 in A[i + 1:]:
				cols2 = d[r2]
				s = sorted(cols1 & cols2)
				for (c1, c2) in zip(s[:-1], s[1:]):
					area = (r1 - r2) * (c1 - c2)
					if area < ans:
						ans = area
		return ans if ans < float('inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		d = defaultdict(set)
		(rset, cset, N, ans) = (set(), set(), len(points), float('inf'))
		for (r, c) in points:
			rset.add(r)
			cset.add(c)
		(Nr, Nc) = (len(rset), len(cset))
		if Nr == 1 or Nc == 1:
			return 0
		elif Nr < Nc:
			for (r, c) in points:
				d[r].add(c)
		else:
			for (r, c) in points:
				d[c].add(r)
		A = sorted(d.keys())
		for (i, r1) in enumerate(A):
			cols1 = d[r1]
			for r2 in A[i + 1:]:
				cols2 = d[r2]
				s = sorted(cols1 & cols2)
				for (c1, c2) in zip(s[:-1], s[1:]):
					area = abs((r1 - r2) * (c1 - c2))
					ans = min(ans, area)
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		countx = len(set((x for (x, y) in points)))
		county = len(set((y for (x, y) in points)))
		if countx == n or county == n:
			return 0
		container = defaultdict(list)
		if countx > county:
			for (x, y) in points:
				container[x].append(y)
		else:
			for (x, y) in points:
				container[y].append(x)
		lastx = {}
		ans = float('inf')
		for x in sorted(container):
			container[x].sort()
			for y in range(len(container[x])):
				for z in range(y):
					(y1, y2) = (container[x][z], container[x][y])
					if (y1, y2) in lastx:
						ans = min(ans, (x - lastx[y1, y2]) * abs(y2 - y1))
					lastx[y1, y2] = x
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		d_x = collections.defaultdict(set)
		d_y = collections.defaultdict(set)
		for (x, y) in points:
			d_x[x].add(y)
			d_y[y].add(x)
		area = sys.maxsize
		for (x, y) in points:
			for yy in d_x[x]:
				if yy <= y:
					continue
				for xx in d_y[y]:
					if xx > x and yy in d_x[xx]:
						area = min(area, (xx - x) * (yy - y))
		return area if area != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = collections.defaultdict(list)
		for (x, y) in points:
			columns[x].append(y)
		lastx = {}
		ans = float('inf')
		for x in sorted(columns):
			column = columns[x]
			column.sort()
			for (j, y2) in enumerate(column):
				for i in range(j):
					y1 = column[i]
					if (y1, y2) in lastx:
						ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
					lastx[y1, y2] = x
		return ans if ans < float('inf') else 0


import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		p = collections.defaultdict(list)
		for (x, y) in points:
			p[x].append(y)
		lastx = {}
		res = float('inf')
		for x in sorted(p):
			p[x].sort()
			for i in range(len(p[x])):
				for j in range(i):
					(y1, y2) = (p[x][j], p[x][i])
					if (y1, y2) in lastx:
						res = min(res, (x - lastx[y1, y2]) * (y2 - y1))
					lastx[y1, y2] = x
		return res if res < float('inf') else 0


import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		sameX = collections.defaultdict(list)
		for (x, y) in points:
			sameX[x].append(y)
		lastX = {}
		minArea = float('inf')
		for x in sorted(sameX):
			sameX[x].sort()
			for i in range(len(sameX[x])):
				for j in range(i):
					(y1, y2) = (sameX[x][j], sameX[x][i])
					if (y1, y2) in lastX:
						minArea = min(minArea, (y2 - y1) * (x - lastX[y1, y2]))
					lastX[y1, y2] = x
		return minArea if minArea != float('inf') else 0


import numpy as np
import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		col = collections.defaultdict(list)
		lastx = {}
		ans = float('inf')
		for (x, y) in points:
			col[x].append(y)
		for (x, col_item) in sorted(col.items()):
			col_item = sorted(col_item)
			for i in range(len(col_item)):
				y2 = col_item[i]
				for j in range(i):
					y1 = col_item[j]
					x1 = lastx.get((y1, y2))
					if x1 != None:
						ans = min(ans, (x - x1) * (y2 - y1))
					lastx[y1, y2] = x
		if ans < float('inf'):
			return ans
		else:
			return 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = defaultdict(list)
		points = sorted(points, key=lambda x: (x[0], x[1]))
		for (x, y) in points:
			columns[x].append(y)
		most_recent = {}
		min_area = float('inf')
		for x in columns:
			column = columns[x]
			for (index, y2) in enumerate(column):
				for y1 in column[:index]:
					if (y1, y2) in most_recent:
						min_area = min(min_area, (y2 - y1) * (x - most_recent[y1, y2]))
					most_recent[y1, y2] = x
		return min_area if min_area < float('inf') else 0


class Solution:

	def minAreaRect(self, points):
		n = len(points)
		nx = len(set((x for (x, y) in points)))
		ny = len(set((y for (x, y) in points)))
		if nx == n or ny == n:
			return 0
		p = collections.defaultdict(list)
		if nx > ny:
			for (x, y) in points:
				p[x].append(y)
		else:
			for (x, y) in points:
				p[y].append(x)
		lastx = {}
		res = float('inf')
		for x in sorted(p):
			p[x].sort()
			for i in range(len(p[x])):
				for j in range(i):
					(y1, y2) = (p[x][j], p[x][i])
					if (y1, y2) in lastx:
						res = min(res, (x - lastx[y1, y2]) * abs(y2 - y1))
					lastx[y1, y2] = x
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		cache_x = defaultdict(set)
		cache_y = defaultdict(set)
		cache = set()
		for (i, p) in enumerate(points):
			cache_x[p[0]].add(i)
			cache_y[p[1]].add(i)
			cache.add((p[0], p[1]))
		res = float('inf')
		for (i, (x0, y0)) in enumerate(points):
			cache_x[x0].remove(i)
			cache_y[y0].remove(i)
			cache.remove((x0, y0))
			for ix in cache_y[y0]:
				for iy in cache_x[x0]:
					(x1, y1) = (points[ix][0], points[iy][1])
					if (x1, y1) in cache:
						res = min(res, abs(x1 - x0) * abs(y1 - y0))
		return 0 if res == float('inf') else res


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x_groups = defaultdict(list)
		for pnt in points:
			x_groups[pnt[0]].append(pnt[1])
		pair2x = dict()
		min_area = float('inf')
		for x in sorted(x_groups):
			group = x_groups[x]
			group.sort()
			for i in range(len(group)):
				for j in range(i + 1, len(group)):
					last_x = pair2x.get((group[i], group[j]))
					if last_x is not None:
						min_area = min(min_area, (x - last_x) * (group[j] - group[i]))
					pair2x[group[i], group[j]] = x
		return min_area if min_area < float('inf') else 0


class Solution:

	def minAreaRect(self, points):
		(seen, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y:
					area = abs((p2x - p1x) * (p2y - p1y))
					if area > ans or area == 0:
						continue
					if (p1x, p2y) in seen and (p2x, p1y) in seen:
						ans = area
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort(key=lambda x: (x[0], x[1]))
		mx_y = defaultdict(list)
		for (x, y) in points:
			mx_y[x].append(y)
		res = float('inf')
		seenY_pairs = {}
		for x in mx_y:
			if len(mx_y[x]) < 2:
				continue
			for i in range(len(mx_y[x]) - 1):
				y1 = mx_y[x][i]
				for j in range(i + 1, len(mx_y[x])):
					y2 = mx_y[x][j]
					if (y1, y2) in seenY_pairs:
						width = x - seenY_pairs[y1, y2]
						height = y2 - y1
						res = min(res, width * height)
					seenY_pairs[y1, y2] = x
		if res == float('inf'):
			return 0
		else:
			return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		s = set(map(tuple, points))
		dx = collections.defaultdict(list)
		dy = collections.defaultdict(list)
		for (x, y) in points:
			dx[x].append(y)
			dy[y].append(x)
		res = float('inf')
		for x in sorted(dx.keys()):
			for i in range(len(dx[x])):
				y1 = dx[x][i]
				for j in range(i + 1, len(dx[x])):
					y2 = dx[x][j]
					for x1 in dy[y2]:
						if x1 <= x:
							continue
						if (x1, y1) in s:
							res = min(res, abs(x - x1) * abs(y1 - y2))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		h = defaultdict(deque)
		v = defaultdict(deque)
		p = set([(x, y) for (x, y) in points])
		for (x, y) in points:
			h[x].append(y)
			v[y].append(x)
		minArea = float('inf')
		for (x, y) in points:
			for y1 in h[x]:
				if y1 != y:
					for x1 in v[y]:
						if x1 != x:
							if (x1, y1) in p:
								minArea = min(minArea, abs(y1 - y) * abs(x1 - x))
			if h[x]:
				h[x].popleft()
			if v[y]:
				v[y].popleft()
		if minArea == float('inf'):
			return 0
		return minArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		record = {}
		points.sort(key=lambda x: [x[0], x[1]])
		res = float('inf')
		temp = [points[0][1]]
		for i in range(1, len(points)):
			if points[i][0] == points[i - 1][0]:
				temp.append(points[i][1])
			else:
				if len(temp) >= 2:
					for j in range(len(temp) - 1):
						for k in range(j + 1, len(temp)):
							if (temp[j], temp[k]) in record:
								res = min(res, (points[i - 1][0] - record[temp[j], temp[k]]) * (temp[k] - temp[j]))
							record[temp[j], temp[k]] = points[i - 1][0]
				temp = [points[i][1]]
		if len(temp) >= 2:
			for j in range(len(temp) - 1):
				for k in range(j + 1, len(temp)):
					if (temp[j], temp[k]) in record:
						res = min(res, (points[-1][0] - record[temp[j], temp[k]]) * (temp[k] - temp[j]))
		if res == float('inf'):
			return 0
		return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		col = defaultdict(list)
		for (x, y) in points:
			col[x].append(y)
		res = float('inf')
		pre = defaultdict(int)
		for x in sorted(col):
			col[x].sort()
			for i in range(len(col[x]) - 1):
				for j in range(i + 1, len(col[x])):
					if (col[x][i], col[x][j]) in pre:
						res = min(res, (col[x][j] - col[x][i]) * (x - pre[col[x][i], col[x][j]]))
					pre[col[x][i], col[x][j]] = x
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = defaultdict(list)
		lastx = {}
		ans = sys.maxsize
		for (x, y) in points:
			columns[x].append(y)
		for x in sorted(columns):
			y_list = columns[x]
			y_list.sort()
			for (i, y1) in enumerate(y_list):
				for j in range(i):
					y2 = y_list[j]
					if (y1, y2) in lastx:
						ans = min(ans, (x - lastx[y1, y2]) * (y1 - y2))
					lastx[y1, y2] = x
		return ans if ans < sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		sorted_points = {}
		for point in points:
			if point[0] not in sorted_points:
				sorted_points[point[0]] = []
			sorted_points[point[0]].append(point)
		sorted_col = sorted(sorted_points.keys())
		min_area = None
		seen = {}
		for col in sorted_col:
			sorted_points[col] = sorted(sorted_points[col])
			for idx1 in range(len(sorted_points[col])):
				for idx2 in range(idx1 + 1, len(sorted_points[col])):
					point1 = sorted_points[col][idx1]
					point2 = sorted_points[col][idx2]
					if (point1[1], point2[1]) in seen:
						temp = (point2[1] - point1[1]) * (col - seen[point1[1], point2[1]])
						min_area = min(min_area, temp) if min_area is not None else temp
					seen[point1[1], point2[1]] = col
		return min_area if min_area is not None else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = defaultdict(list)
		for (x, y) in points:
			columns[x].append(y)
		(seen, result) = ({}, float('inf'))
		for x2 in sorted(columns):
			column = columns[x2]
			column.sort()
			for (j, y2) in enumerate(column):
				for i in range(j):
					y1 = column[i]
					if (y1, y2) in seen:
						result = min(result, (x2 - seen[y1, y2]) * (y2 - y1))
					seen[y1, y2] = x2
		return result if result != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		nx = len(set((x for (x, _) in points)))
		ny = len(set((y for (_, y) in points)))
		if nx == n and ny == n:
			return False
		p = collections.defaultdict(list)
		if nx > ny:
			for (x, y) in points:
				p[x].append(y)
		else:
			for (x, y) in points:
				p[y].append(x)
		last_x = {}
		area = float('inf')
		for x in sorted(p):
			p[x].sort()
			for i in range(len(p[x])):
				for j in range(i):
					(y1, y2) = (p[x][j], p[x][i])
					if (y1, y2) in last_x:
						area = min(area, (x - last_x[y1, y2]) * (y2 - y1))
					last_x[y1, y2] = x
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xtoy = collections.defaultdict(set)
		for (x, y) in points:
			xtoy[x].add(y)
		minarea = sys.maxsize
		for x1 in xtoy:
			for x2 in xtoy:
				if x1 >= x2:
					continue
				commony = list(xtoy[x1].intersection(xtoy[x2]))
				if len(commony) < 2:
					continue
				commony.sort()
				width = x2 - x1
				height = commony[1] - commony[0]
				for i in range(2, len(commony)):
					height = min(height, commony[i] - commony[i - 1])
				minarea = min(minarea, height * width)
		return minarea if minarea != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		ret = float('inf')
		r_to_c = collections.defaultdict(list)
		for (r, c) in points:
			r_to_c[r].append(c)
		seen = {}
		for bottom in sorted(r_to_c.keys()):
			cols = r_to_c[bottom]
			cols.sort()
			for right_i in range(len(cols)):
				for left_i in range(right_i):
					left = cols[left_i]
					right = cols[right_i]
					if (left, right) in seen:
						top = seen[left, right]
						ret = min(ret, (bottom - top) * (right - left))
					seen[left, right] = bottom
		if ret == float('inf'):
			return 0
		return ret


from itertools import combinations

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		area = float('inf')
		by_x = {}
		visited = {}
		for point in points:
			by_x[point[0]] = []
		for point in points:
			by_x[point[0]].append(point[1])
		for x in sorted(by_x):
			for (y1, y2) in combinations(sorted(by_x[x]), 2):
				if (y1, y2) in visited:
					area = min(area, abs(x - visited[y1, y2]) * abs(y2 - y1))
				visited[y1, y2] = x
		return area if area != float('inf') else 0


from collections import defaultdict
from itertools import combinations
import sys

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		coordMap = defaultdict(set)
		for (x, y) in points:
			coordMap[x].add(y)
		ans = sys.maxsize
		for (x1, x2) in combinations(list(coordMap.keys()), 2):
			ylist = coordMap[x1].intersection(coordMap[x2])
			if len(ylist) < 2:
				continue
			ylist = sorted(list(ylist))
			idx = min(list(range(len(ylist) - 1)), key=lambda i: ylist[i + 1] - ylist[i])
			h = ylist[idx + 1] - ylist[idx]
			ans = min(ans, abs(x2 - x1) * h)
		return ans if ans != sys.maxsize else 0


import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = {}
		for (x, y) in points:
			if x not in columns:
				columns[x] = []
			columns[x].append(y)
		lastx = {}
		ans = float('inf')
		for x in sorted(columns.keys()):
			column = columns[x]
			column.sort()
			for (i, v) in enumerate(column):
				for j in range(i):
					val = column[j]
					if (val, v) in lastx:
						ans = min(ans, (x - lastx[val, v]) * (v - val))
					lastx[val, v] = x
		return ans if ans < float('inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		points.sort()
		(d, ans) = (defaultdict(set), float('inf'))
		for (r, c) in points:
			d[r].add(c)
		A = list(d.keys())
		for (i, r1) in enumerate(A):
			cols1 = d[r1]
			for r2 in A[i + 1:]:
				cols2 = d[r2]
				s = sorted(cols1 & cols2)
				for (c1, c2) in zip(s[:-1], s[1:]):
					area = (r1 - r2) * (c1 - c2)
					if area < ans:
						ans = area
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:

		def compute_table(points, axis=0):
			table = {}
			for point in points:
				(key, value) = (point[axis], point[1 - axis])
				if key in table:
					table[key].append(value)
				else:
					table[key] = [value]
			return table
		points.sort()
		x_2_y = compute_table(points, 0)
		y_2_x = compute_table(points, 1)
		min_area = float('inf')
		hashed = set([tuple(point) for point in points])
		for point in points:
			(x, y) = point
			y_candidates = [_y for _y in x_2_y[x] if _y > y]
			x_candidates = [_x for _x in y_2_x[y] if _x > x]
			for c_y in y_candidates:
				for c_x in x_candidates:
					if (c_x, c_y) in hashed:
						min_area = min(min_area, abs(c_y - y) * abs(c_x - x))
		if min_area == float('inf'):
			return 0
		return min_area


from collections import defaultdict
from itertools import combinations
import sys

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		coordMap = defaultdict(list)
		visited = {}
		for (x, y) in points:
			coordMap[x].append(y)
		ans = sys.maxsize
		for x in sorted(coordMap):
			for (y1, y2) in combinations(sorted(coordMap[x]), 2):
				if (y1, y2) in visited:
					ans = min(ans, (x - visited[y1, y2]) * abs(y1 - y2))
				visited[y1, y2] = x
		return ans if ans != sys.maxsize else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		xp = defaultdict(set)
		yp = defaultdict(set)
		for (x, y) in points:
			xp[x].add(y)
			yp[y].add(x)
		a_min = None
		for (x1, ys) in xp.items():
			if len(ys) < 2:
				continue
			for y1 in ys:
				for y2 in ys:
					if y1 >= y2:
						continue
					for x2 in yp.get(y2, []):
						if x1 >= x2:
							continue
						if y1 in xp[x2]:
							area = (x2 - x1) * (y2 - y1)
							if a_min is None:
								a_min = area
							else:
								a_min = min(area, a_min)
		if a_min is None:
			return 0
		return a_min


import math
from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		horizontal_lines = defaultdict(set)
		vertical_lines = defaultdict(set)
		for (x, y) in points:
			vertical_lines[x].add(y)
			horizontal_lines[y].add(x)
		min_area = math.inf
		for (x, y) in points:
			for next_y in vertical_lines[x]:
				if next_y > y:
					for intersect_x in horizontal_lines[y] & horizontal_lines[next_y]:
						if intersect_x < x:
							min_area = min((x - intersect_x) * (next_y - y), min_area)
		if min_area == math.inf:
			return 0
		else:
			return min_area


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		rows = defaultdict(list)
		for (i, j) in points:
			rows[i].append(j)
		result = float('inf')
		lastRow = {}
		for row in sorted(rows.keys()):
			cols = rows[row]
			cols.sort()
			for (j, col2) in enumerate(cols):
				for i in range(j):
					col1 = cols[i]
					if (col1, col2) in lastRow:
						result = min(result, (row - lastRow[col1, col2]) * (col2 - col1))
					lastRow[col1, col2] = row
		return result if result != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		lines = self.find_lines(points)
		min_area = 0
		d = {}
		for (x, ys) in lines:
			if ys in d:
				px = d[ys]
				curr_min_area = abs(x - px) * abs(ys[0] - ys[1])
				min_area = min(min_area, curr_min_area) if min_area > 0 else curr_min_area
			d[ys] = x
		return min_area

	def find_lines(self, points: List[List[int]]) -> List[Tuple[int, Tuple[int, int]]]:
		ps = defaultdict(list)
		for (x, y) in sorted(points):
			ps[x].append(y)
		lines = []
		for (x, ys) in ps.items():
			for (i, y0) in enumerate(ys):
				for y1 in ys[i + 1:]:
					lines.append((x, (y0, y1)))
		return lines


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort(key=lambda x: (x[0], x[1]))
		heights = defaultdict(list)
		for point in points:
			(x, h) = point
			heights[x].append(h)
		segments = {}
		keys = list(heights.keys())
		keys.sort()
		min_area = float('inf')
		for x in keys:
			heights_x = heights[x]
			if len(heights_x) < 2:
				continue
			for i in range(len(heights_x) - 1):
				for j in range(i + 1, len(heights_x)):
					pair = (heights_x[i], heights_x[j])
					if pair not in segments:
						segments[pair] = [None, x]
					else:
						height_diff = heights_x[j] - heights_x[i]
						width_diff = x - segments[pair][1]
						area = height_diff * width_diff
						min_area = min(min_area, area)
						segments[pair] = [segments[pair][1], x]
		if min_area == float('inf'):
			return 0
		else:
			return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		xs = collections.defaultdict(list)
		ys = collections.defaultdict(list)
		for (x, y) in points:
			xs[x].append(y)
			ys[y].append(x)
		result = math.inf
		for (x0, ylist) in xs.items():
			for (y1, y2) in itertools.combinations(ylist, 2):
				(xlist1, xlist2) = (ys[y1], ys[y2])
				(m, n) = (len(xlist1), len(xlist2))
				i = bisect.bisect(xlist1, x0)
				if i == m:
					continue
				j = bisect.bisect(xlist2, x0)
				if j == n:
					continue
				while i < m and j < n:
					if xlist1[i] < xlist2[j]:
						i += 1
					elif xlist1[i] > xlist2[j]:
						j += 1
					else:
						result = min(result, (xlist1[i] - x0) * (y2 - y1))
						break
		return 0 if math.isinf(result) else result


import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		dic = collections.defaultdict(list)
		for (x, y) in points:
			dic[x].append(y)
		res = float('inf')
		store = {}
		for x in sorted(dic):
			col = sorted(dic[x])
			for (i, y1) in enumerate(col):
				for j in range(i):
					if (y1, col[j]) not in store:
						store[y1, col[j]] = x
					else:
						res = min(res, (y1 - col[j]) * (x - store[y1, col[j]]))
						store[y1, col[j]] = x
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		table = {}
		mark = []
		best = 0
		for i in points:
			if i[0] not in table:
				table[i[0]] = [[i[1]], []]
			elif i[1] not in table[i[0]][0]:
				for j in table[i[0]][0]:
					if j < i[1]:
						table[i[0]][1].append((j, i[1]))
					else:
						table[i[0]][1].append((i[1], j))
				table[i[0]][0].append(i[1])
				if len(table[i[0]][0]) == 2:
					mark.append(i[0])
		g = {}
		if len(mark) < 2:
			return 0
		for i in mark:
			p = table[i]
			for j in p[1]:
				if j in g:
					for k in g[j]:
						temp = abs((k - i) * (j[1] - j[0]))
						if best == 0 or temp < best:
							best = temp
					g[j].append(i)
				else:
					g[j] = [i]
		return best


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		if n < 4:
			return 0
		s = set([tuple(i) for i in points])
		d = {}
		for i in points:
			if i[0] in d:
				d[i[0]].append(i[1])
			else:
				d[i[0]] = [i[1]]
		for i in list(d.keys()):
			if len(d[i]) == 1:
				d.pop(i)
		dkeys = list(d.keys())
		minarea = float('inf')
		for i in range(len(dkeys) - 1):
			if len(points[i]) == 1:
				continue
			for x in range(len(d[dkeys[i]]) - 1):
				for y in range(x + 1, len(d[dkeys[i]])):
					for j in range(i + 1, len(dkeys)):
						if (dkeys[j], d[dkeys[i]][x]) in s and (dkeys[j], d[dkeys[i]][y]) in s:
							minarea = min(minarea, abs(dkeys[i] - dkeys[j]) * abs(d[dkeys[i]][x] - d[dkeys[i]][y]))
		if minarea == float('inf'):
			return 0
		return minarea


class Solution(object):

	def minAreaRect(self, points):
		seen = set()
		res = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area < res:
						res = area
			seen.add((x1, y1))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		(nx, ny) = (len(set((x for (x, _) in points))), len(set((y for (_, y) in points))))
		if nx == n or ny == n:
			return 0
		p = collections.defaultdict(list)
		if nx > ny:
			for (x, y) in points:
				p[x].append(y)
		else:
			for (x, y) in points:
				p[y].append(x)
		res = float('inf')
		dic_last = {}
		for (x1, x2) in itertools.combinations(p, 2):
			if len(p[x1]) < 2 or len(p[x2]) < 2:
				continue
			for (y1, y2) in itertools.combinations(sorted(set(p[x1]) & set(p[x2])), 2):
				res = min(res, abs(x1 - x2) * (y2 - y1))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		result = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area < result:
						result = area
			seen.add((x1, y1))
		return result if result != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		points_set = set([tuple(point) for point in points])
		smallest = float('inf')
		for (i, (x1, y1)) in enumerate(points):
			for (j, (x2, y2)) in enumerate(points[i:]):
				if x1 < x2 and y1 < y2 and ((x1, y2) in points_set) and ((x2, y1) in points_set):
					area = (x2 - x1) * (y2 - y1)
					smallest = min(smallest, area)
		return smallest if smallest != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		minv = float('inf')
		for (x, y) in points:
			for (a, b) in seen:
				if x != a and y != b and ((x, b) in seen) and ((a, y) in seen):
					minv = min(minv, abs(a - x) * abs(y - b))
			seen.add((x, y))
		return minv if minv != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = inf = float('inf')
		seen = set()
		n = len(points)
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					res = min(res, abs((x2 - x1) * (y2 - y1)))
			seen.add((x1, y1))
		return res if res != inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		area = float('inf')
		seen = set()
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if x1 != x2 and y1 != y2:
					if (x1, y2) in seen and (x2, y1) in seen:
						(l, w) = (abs(x1 - x2), abs(y1 - y2))
						area = min(area, l * w)
			seen.add((x1, y1))
		return 0 if area == float('inf') else area


class Solution(object):

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		setx = set()
		sety = set()
		for (x, y) in points:
			setx.add(x)
			sety.add(y)
		nx = len(setx)
		ny = len(sety)
		if nx == n or ny == n:
			return 0
		p = collections.defaultdict(list)
		if nx > ny:
			for (x, y) in points:
				p[x].append(y)
		else:
			for (x, y) in points:
				p[y].append(x)
		res = float('inf')
		dic_last = {}
		for x in sorted(p):
			p[x].sort()
			for (y1, y2) in itertools.combinations(p[x], 2):
				if (y1, y2) in dic_last:
					res = min(res, (x - dic_last[y1, y2]) * (y2 - y1))
				dic_last[y1, y2] = x
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		visited = set()
		output = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in visited:
				if (x1, y2) in visited and (x2, y1) in visited:
					temp = abs(x2 - x1) * abs(y2 - y1)
					if temp < output:
						output = temp
			visited.add((x1, y1))
		return output if output != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		min_area = float('inf')
		seen = set()
		poi = []
		for (x, y) in points:
			poi.append((x, y))
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area < min_area:
						min_area = area
			seen.add((x1, y1))
		return min_area if min_area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		seen = set()
		minarea = sys.maxsize
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					minarea = min(minarea, abs(x2 - x1) * abs(y2 - y1))
			seen.add((x1, y1))
		return minarea if minarea < sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = float('inf')
		lookup = set()
		for (x1, y1) in points:
			for (x2, y2) in lookup:
				if (x1, y2) in lookup and (x2, y1) in lookup:
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
			lookup.add((x1, y1))
		return res if res != float('inf') else 0
		ys_with_same_x = defaultdict(list)
		for (x, y) in points:
			ys_with_same_x[x].append(y)
		pair_of_ys_history = {}
		res = float('inf')
		for (x, ys) in sorted(ys_with_same_x.items()):
			ys.sort()
			for (i, y1) in enumerate(ys):
				for j in range(i):
					y2 = ys[j]
					if (y1, y2) in pair_of_ys_history:
						res = min(res, (x - pair_of_ys_history[y1, y2]) * (y1 - y2))
					pair_of_ys_history[y1, y2] = x
		if res == float('inf'):
			return 0
		else:
			return res


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		res = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
			seen.add((x1, y1))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set(((x, y) for (x, y) in points))
		min_rec = math.inf
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 < x2 and y1 > y2:
					if (x1, y2) in point_set and (x2, y1) in point_set:
						min_rec = min(min_rec, (x2 - x1) * (y1 - y2))
		return 0 if min_rec == math.inf else min_rec


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		min_area = float('inf')
		seen = set()
		for (x0, y0) in points:
			for (x1, y1) in seen:
				if (x0, y1) in seen and (x1, y0) in seen:
					current_area = abs(y1 - y0) * abs(x1 - x0)
					min_area = min(min_area, current_area)
			seen.add((x0, y0))
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:

		def smallestinterval(l):
			rst = float('inf')
			for i in range(1, len(l)):
				if l[i] - l[i - 1] < rst:
					rst = l[i] - l[i - 1]
			return rst
		xloc = defaultdict(set)
		for p in points:
			xloc[p[0]].add(p[1])
		minarea = float('inf')
		xkeys = list(xloc.keys())
		for x1 in xkeys:
			for x2 in xkeys:
				if x1 != x2:
					sharedy = xloc[x1] & xloc[x2]
					if len(sharedy) > 1:
						ally = list(sharedy)
						ally.sort()
						smallinterval = smallestinterval(ally)
						if smallinterval * abs(x1 - x2) < minarea:
							minarea = smallinterval * abs(x1 - x2)
		if minarea == float('inf'):
			return 0
		return minarea


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		(Nr, Nc) = (len(set(X[0])), len(set(X[1])))
		if Nr == 1 or Nc == 1:
			return 0
		if Nr < Nc:
			points = [[c, r] for (r, c) in points]
			return self.minAreaRect(points)
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in columns.items():
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						area = (r - lastc[c1, c2]) * (c2 - c1)
						if area < ans:
							ans = area
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		min_area = math.inf
		seen = set()
		for (x0, y0) in points:
			for (x1, y1) in seen:
				if (x0, y1) in seen and (x1, y0) in seen:
					area = abs(x0 - x1) * abs(y0 - y1)
					if area > 0:
						min_area = min(min_area, area)
			seen.add((x0, y0))
		return 0 if min_area == math.inf else min_area


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		area = float('inf')
		gx = defaultdict(list)
		gy = defaultdict(list)
		for p in points:
			[x1, y1] = p
			if x1 in gx and y1 in gy:
				for y2 in gx[x1]:
					if y2 in gy:
						for x2 in gy[y2]:
							if x2 in gy[y1]:
								area = min(area, abs(x1 - x2) * abs(y1 - y2))
			gx[x1].append(y1)
			gy[y1].append(x1)
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		group_x_coords = collections.defaultdict(list)
		group_y_coords = collections.defaultdict(set)
		for point in points:
			group_x_coords[point[0]].append(point[1])
			group_y_coords[point[1]].add(point[0])
		min_area = float('inf')
		for key in group_x_coords.keys():
			if len(group_x_coords[key]) < 2:
				continue
			for i in range(len(group_x_coords[key])):
				for j in range(i + 1, len(group_x_coords[key])):
					y_val_1 = group_x_coords[key][i]
					y_val_2 = group_x_coords[key][j]
					common_x_coords = group_y_coords[y_val_1] & group_y_coords[y_val_2]
					if len(common_x_coords) > 1:
						y_diff = abs(y_val_1 - y_val_2)
						x_diff = float('inf')
						for ele in common_x_coords:
							if ele == key:
								continue
							if abs(ele - key) < x_diff:
								x_diff = abs(ele - key)
						area = x_diff * y_diff
						if area < min_area:
							min_area = area
		if min_area == float('inf'):
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		rows = collections.defaultdict(list)
		points.sort()
		seen = set()
		result = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if x1 < x2 and y1 < y2:
					continue
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area < result:
						result = area
			seen.add((x1, y1))
		return result if result < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		globalMinArea = float('inf')
		a = set()
		for (x, y) in points:
			for (x1, y1) in a:
				if (x, y1) in a and (x1, y) in a:
					currentMinArea = abs(x - x1) * abs(y - y1)
					globalMinArea = min(globalMinArea, currentMinArea)
			a.add((x, y))
		return globalMinArea if globalMinArea < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		res = float('inf')
		for point in points:
			(x, y) = (point[0], point[1])
			for (_x, _y) in seen:
				if (x, _y) in seen and (_x, y) in seen:
					res = min(res, abs(x - _x) * abs(y - _y))
			seen.add((x, y))
		if res == float('inf'):
			return 0
		return res


class Solution(object):

	def minAreaRect(self, points):
		min_area = sys.maxsize
		points_table = set()
		for (x, y) in points:
			points_table.add((x, y))
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 > x2 and y1 > y2:
					if (x1, y2) in points_table and (x2, y1) in points_table:
						area = abs(x1 - x2) * abs(y1 - y2)
						if area:
							min_area = min(area, min_area)
		return 0 if min_area == sys.maxsize else min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		hs = set()
		N = len(points)
		res = float('inf')
		for i in range(N):
			(x1, y1) = points[i]
			for (x2, y2) in hs:
				if (x1, y2) in hs and (x2, y1) in hs:
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
			hs.add((x1, y1))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ans = float('inf')
		s = set()
		for (i, j) in points:
			for (x, y) in s:
				if (i, y) in s and (x, j) in s:
					ans = min(ans, abs(i - x) * abs(j - y))
			s.add((i, j))
		return ans if ans != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		best = 0
		for p1 in points:
			(x1, y1) = p1
			for p2 in seen:
				(x2, y2) = p2
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x2 - x1) * abs(y2 - y1)
					if best == 0:
						best = area
					else:
						best = min(best, area)
			seen.add((x1, y1))
		return best


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		min_area = float('inf')
		points_table = set()
		for (x, y) in points:
			points_table.add((x, y))
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 > x2 and y1 > y2:
					if (x1, y2) in points_table and (x2, y1) in points_table:
						area = abs(x1 - x2) * abs(y1 - y2)
						if area:
							min_area = min(area, min_area)
		return 0 if min_area == float('inf') else min_area


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		(setr, setc) = (set(), set())
		for (r, c) in points:
			setr.add(r)
			setc.add(c)
		if len(points) in (len(setr), len(setc)):
			return 0
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for r in sorted(columns):
			cols = sorted(columns[r])
			for (j, y2) in enumerate(cols):
				for (i, y1) in enumerate(cols[:j]):
					if (y1, y2) in lastc:
						ans = min(ans, (r - lastc[y1, y2]) * (y2 - y1))
					lastc[y1, y2] = r
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		if len(points) in (len(set(X[0])), len(set(X[1]))):
			return 0
		(seen, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y and ((p1x, p2y) in seen) and ((p2x, p1y) in seen):
					ans = min(ans, abs((p1x - p2x) * (p1y - p2y)))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set(((x, y) for (x, y) in points))
		min_rec = math.inf
		points.sort()
		for idx1 in range(len(points)):
			for idx2 in range(idx1 + 1, len(points)):
				(x1, y1) = points[idx1]
				(x2, y2) = points[idx2]
				if x1 < x2 and y1 > y2:
					if (x1, y2) in point_set and (x2, y1) in point_set:
						min_rec = min(min_rec, (x2 - x1) * (y1 - y2))
		return 0 if min_rec == math.inf else min_rec


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		for point in points:
			seen.add((point[0], point[1]))
		min_area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 > x2 and y1 > y2:
					if (x1, y2) in seen and (x2, y1) in seen:
						area = abs(y2 - y1) * abs(x2 - x1)
						min_area = min(min_area, area)
		return 0 if min_area == float('inf') else min_area


import math

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = set(map(tuple, points))
		min_area = math.inf
		for (start_x, start_y) in points:
			for (diag_x, diag_y) in points:
				if diag_y < start_y and diag_x > start_x and ((diag_x, start_y) in points) and ((start_x, diag_y) in points):
					min_area = min(min_area, (diag_x - start_x) * (start_y - diag_y))
		if min_area == math.inf:
			return 0
		else:
			return min_area


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = set()
		for (x, y) in points:
			points_set.add((x, y))
		min_area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x2 > x1 and y2 > y1:
					if (x2, y1) in points_set and (x1, y2) in points_set:
						area = abs(x1 - x2) * abs(y1 - y2)
						min_area = min(min_area, area)
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ys = {}
		for (x, y) in points:
			if y not in ys:
				ys[y] = set()
			ys[y].add(x)
		result = -1
		for y1 in ys:
			for y2 in ys:
				if y1 == y2:
					continue
				points = ys[y1].intersection(ys[y2])
				if len(points) < 2:
					continue
				points = list(points)
				points.sort()
				x1 = points[0]
				for i in range(1, len(points)):
					x2 = points[i]
					area = (x2 - x1) * abs(y2 - y1)
					if result < 0:
						result = area
					else:
						result = min(area, result)
					x1 = x2
		return result if result >= 0 else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:

		def calculateArea(x1, x2, y1, y2):
			return abs(y2 - y1) * abs(x2 - x1)
		if not points or len(points) < 4:
			return 0
		visited = set()
		area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in visited:
				if (x1, y2) in visited and (x2, y1) in visited:
					area = min(area, calculateArea(x1, x2, y1, y2))
			visited.add((x1, y1))
		return area if area != float('inf') else 0


from collections import defaultdict
from math import inf

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		byrow = defaultdict(set)
		bycol = defaultdict(list)
		for (x, y) in points:
			byrow[y].add(x)
			bycol[x].append(y)
		area = inf
		for (x1, ys) in list(bycol.items()):
			if len(ys) < 2:
				continue
			for (j, y1) in enumerate(ys):
				for y2 in ys[j + 1:]:
					lens = [abs(x1 - x2) for x2 in byrow[y1] & byrow[y2] - {x1}]
					if lens:
						area = min(area, min(lens) * abs(y1 - y2))
		return area if area < inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		saw = set()
		res = float('inf')
		for (x, y) in points:
			for (dx, dy) in saw:
				p1 = (dx, y)
				p2 = (x, dy)
				if p1 in saw and p2 in saw and (dx != x) and (dy != y):
					res = min(res, abs(dx - x) * abs(dy - y))
			saw.add((x, y))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		min_area = 40000 * 40000 + 1
		seen_points = set()
		for (x, y) in points:
			seen_points.add((x, y))
		for (p1_x, p1_y) in points:
			for (p2_x, p2_y) in points:
				if p1_x > p2_x and p1_y > p2_y:
					if (p1_x, p2_y) in seen_points and (p2_x, p1_y) in seen_points:
						area = abs(p2_x - p1_x) * abs(p2_y - p1_y)
						if area > 0:
							min_area = min(min_area, area)
		if min_area == 40000 * 40000 + 1:
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points):
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y and ((p1x, p2y) in pSet) and ((p2x, p1y) in pSet):
					ans = min(ans, abs((p1x - p2x) * (p1y - p2y)))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		s = set((tuple(p) for p in points))
		area = math.inf
		for (i, (x1, y1)) in enumerate(points):
			for (x2, y2) in points[i:]:
				if x1 == x2 or y1 == y2:
					continue
				if (x2, y1) not in s or (x1, y2) not in s:
					continue
				area = min(area, abs((x2 - x1) * (y2 - y1)))
		return area if area != math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		dx = defaultdict(list)
		for (x, y) in points:
			dx[x].append(y)
		lastx = defaultdict(list)
		ans = float('inf')
		for x in sorted(dx):
			col = dx[x]
			col.sort()
			for i in range(len(col) - 1):
				for j in range(i + 1, len(col)):
					y1 = col[i]
					y2 = col[j]
					if (y1, y2) in lastx:
						for xs in lastx[y1, y2]:
							ans = min(ans, abs(y2 - y1) * abs(x - xs))
					lastx[y1, y2].append(x)
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		seen = set()
		ans = sys.maxsize
		for (x1, y1) in points:
			for (x2, y2) in seen:
				if (x1, y2) in seen and (x2, y1) in seen:
					area = abs(x1 - x2) * abs(y1 - y2)
					ans = min(ans, area)
			seen.add((x1, y1))
		return ans if ans < sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		counter = Counter(list(map(tuple, points)))
		points = list(counter)
		result = float('inf')
		for (i, (x, y)) in enumerate(points):
			for j in range(i + 1, len(points)):
				(x_, y_) = points[j]
				if x != x_ and y != y_:
					area = abs((x_ - x) * (y_ - y))
					if area < result and (x, y_) in counter and ((x_, y) in counter):
						if not area:
							return 0
						result = area
				elif counter[x, y] == 2 and counter[x_, y_] == 2:
					return 0
		return 0 if result == float('inf') else result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set(map(tuple, points))
		min_area = float('inf')
		for (i, (x1, y1)) in enumerate(points):
			for (x2, y2) in points[:i]:
				if x1 != x2 and y1 != y2:
					if (x1, y2) in point_set and (x2, y1) in point_set:
						min_area = min(min_area, abs((x2 - x1) * (y2 - y1)))
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		appeared = set()
		res = math.inf
		for (x1, y1) in points:
			for (x2, y2) in appeared:
				if (x1, y2) in appeared and (x2, y1) in appeared:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area < res:
						res = area
			appeared.add((x1, y1))
		return 0 if res == math.inf else res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		cols = defaultdict(list)
		for p in points:
			cols[p[0]].append(p[1])
		last_x = {}
		ans = float('inf')
		for x in sorted(cols):
			for i in range(len(cols[x])):
				for j in range(i + 1, len(cols[x])):
					if (cols[x][i], cols[x][j]) in last_x:
						ans = min(ans, (cols[x][j] - cols[x][i]) * (x - last_x[cols[x][i], cols[x][j]]))
					last_x[cols[x][i], cols[x][j]] = x
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		(nx, ny) = (len(set((x for (x, _) in points))), len(set((y for (_, y) in points))))
		if nx == n or ny == n:
			return 0
		p = collections.defaultdict(list)
		if nx > ny:
			for (x, y) in points:
				p[x].append(y)
		else:
			for (x, y) in points:
				p[y].append(x)
		res = float('inf')
		dic_last = {}
		for (x1, x2) in itertools.combinations(p, 2):
			if len(p[x1]) < 2 or len(p[x2]) < 2:
				continue
			(l1, l2) = (sorted(p[x1]), sorted(p[x2]))
			i = j = 0
			y = []
			while i < len(l1) and j < len(l2):
				v = max(l1[i], l2[j])
				if l1[i] < v:
					i += 1
				elif l2[j] < v:
					j += 1
				else:
					y += (v,)
					(i, j) = (i + 1, j + 1)
			for (y1, y2) in itertools.combinations(y, 2):
				res = min(res, abs(x1 - x2) * (y2 - y1))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		length = len(points)
		if length <= 3:
			return 0
		sets = set([])
		for point in points:
			sets.add(tuple(point))
		min_area = float('inf')
		for i in range(length - 1):
			(x1, y1) = points[i]
			for j in range(i + 1, length):
				(x2, y2) = points[j]
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in sets and (x2, y1) in sets:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area < min_area:
						min_area = area
		if min_area == float('inf'):
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		dictY = collections.defaultdict(list)
		for (i, (x, y)) in enumerate(points):
			dictY[y].append(i)
		y2Xpair = collections.defaultdict(set)
		for y in dictY.keys():
			if len(dictY[y]) <= 1:
				continue
			for (p1, p2) in itertools.combinations(dictY[y], 2):
				(x1, _, x2, _) = points[p1] + points[p2]
				y2Xpair[y].add((min(x1, x2), max(x1, x2)))
		res = float('inf')
		for ((y1, p1), (y2, p2)) in itertools.combinations(y2Xpair.items(), 2):
			h = abs(y1 - y2)
			for (x1, x2) in p1 & p2:
				res = min(res, (x2 - x1) * h)
		return 0 if res == float('inf') else res


from math import inf

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) == 0:
			return 0
		(N, min_area) = (len(points), inf)
		d = set()
		for i in range(N):
			d.add(tuple(points[i]))
		for i in range(N):
			for j in range(i + 1, N, 1):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 > x2 and y1 > y2 or (x2 > x1 and y2 > y1):
					if (x1, y2) in d and (x2, y1) in d:
						min_area = min(min_area, (x2 - x1) * (y2 - y1))
		if min_area == inf:
			return 0
		else:
			return min_area


class Solution:

	def minAreaRect(self, points):
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y and ((p1x, p2y) in pSet) and ((p2x, p1y) in pSet):
					ans = min(ans, abs((p1x - p2x) * (p1y - p2y)))
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		if len(set(X[0])) == 1 or len(set(X[1])) == 1:
			return 0
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				area = abs((p2x - p1x) * (p2y - p1y))
				if area > ans or area == 0:
					continue
				if (p1x, p2y) in pSet and (p2x, p1y) in pSet:
					ans = area
		return ans if ans < float('inf') else 0
from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		(Nr, Nc) = (len(set(X[0])), len(set(X[1])))
		if Nr == 1 or Nc == 1:
			return 0
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in list(columns.items()):
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						area = (r - lastc[c1, c2]) * (c2 - c1)
						if area < ans:
							ans = area
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0


from itertools import product

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points or not points[0]:
			return 0
		(m, n) = (len(points), len(points[0]))
		(d_row, d_col) = ({}, {})
		for (r, c) in points:
			d_row[r] = d_row.get(r, []) + [c]
			d_col[c] = d_col.get(c, []) + [r]
		for r in d_row:
			d_row[r] = sorted(d_row[r])
		for c in d_col:
			d_col[c] = sorted(d_col[c])
		area = float('inf')
		for (r, c) in points:
			c2s = [x for x in d_row[r] if x > c]
			r2s = [x for x in d_col[c] if x > r]
			if not c2s or not r2s:
				continue
			for (r2, c2) in product(r2s, c2s):
				if c2 in d_row[r2]:
					area = min(area, (r2 - r) * (c2 - c))
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		from collections import defaultdict
		x_dic = defaultdict(list)
		y_dic = defaultdict(list)
		area = float('inf')
		for (x, y) in points:
			x_dic[x].append(y)
			y_dic[y].append(x)
			for _y in x_dic[x]:
				if _y != y and _y in y_dic:
					for _x in y_dic[_y]:
						if _x != x and _x in x_dic and (y in x_dic[_x]):
							area = min(area, abs(x - _x) * abs(y - _y))
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x_memo = collections.defaultdict(set)
		for (x, y) in points:
			x_memo[x].add(y)
		x_lst = sorted(list(x_memo.keys()))
		res = math.inf
		for i in range(len(x_lst)):
			for j in range(i + 1, len(x_lst)):
				dx = x_lst[j] - x_lst[i]
				y_common = x_memo[x_lst[i]].intersection(x_memo[x_lst[j]])
				if len(y_common) < 2:
					continue
				y_common = sorted(list(y_common))
				for k in range(len(y_common) - 1):
					res = min(res, dx * (y_common[k + 1] - y_common[k]))
		if math.isfinite(res):
			return res
		else:
			return 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		p = collections.defaultdict(set)
		for (x, y) in points:
			p[x].add(y)
		xs = sorted(p.keys())
		minv = float('inf')
		for i in range(len(xs) - 1):
			for j in range(i + 1, len(xs)):
				le = xs[j] - xs[i]
				if le > minv:
					break
				potential = sorted(p[xs[i]].intersection(p[xs[j]]))
				v = float('inf')
				for j in range(len(potential) - 1):
					v = min(v, potential[j + 1] - potential[j])
				minv = min(minv, v * le)
		return minv if minv < float('inf') else 0


class Solution:

	def minAreaRectangularHull(self, points: List[List[int]]) -> int:
		area = 0
		if points:
			(minx, miny) = points[0]
			(maxx, maxy) = points[0]
			for (x, y) in points:
				minx = min(minx, x)
				miny = min(miny, y)
				maxx = max(maxx, x)
				maxy = max(maxy, y)
			area = (maxx - minx) * (maxy - miny)
		return area

	def minAreaRect(self, points):
		S = set(map(tuple, points))
		ans = float('inf')
		for (k, (xB, yB)) in enumerate(points):
			for j in range(k):
				(xA, yA) = points[j]
				if xA != xB and yA != yB and ((xA, yB) in S) and ((xB, yA) in S):
					ans = min(ans, abs((xB - xA) * (yB - yA)))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		mx = defaultdict(set)
		for (x, y) in points:
			mx[x].add(y)
		(ans, n) = (float('inf'), len(points))
		for i in range(n - 1):
			(x1, y1) = points[i]
			for j in range(i + 1, n):
				(x2, y2) = points[j]
				if x2 == x1 or y2 == y1 or y2 not in mx[x1] or (y1 not in mx[x2]):
					continue
				ans = min(abs(x2 - x1) * abs(y2 - y1), ans)
		return 0 if ans == float('inf') else ans


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = {(x, y) for (x, y) in points}
		min_area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 == x2 or y1 == y2:
					continue
				if abs((x1 - x2) * (y1 - y2)) > min_area:
					continue
				if (x1, y2) in points and (x2, y1) in points:
					min_area = min(min_area, abs((x1 - x2) * (y1 - y2)))
		if min_area == float('inf'):
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		(x_lines, y_lines) = ({}, {})
		for (x, y) in points:
			x_lines[x] = x_lines.get(x, set()) | {y}
			y_lines[y] = y_lines.get(y, set()) | {x}
		res = float('inf')
		for (x, y_s) in x_lines.items():
			if len(y_s) < 2:
				continue
			y_s = list(y_s)
			for i in range(len(y_s)):
				for j in range(i + 1, len(y_s)):
					(y1, y2) = (y_s[i], y_s[j])
					inter = y_lines[y1].intersection(y_lines[y2])
					if len(inter) <= 1:
						continue
					for x2 in inter:
						if x2 == x:
							continue
						res = min(res, abs(y1 - y2) * abs(x - x2))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		x_vals = defaultdict(set)
		y_vals = defaultdict(set)
		for p in points:
			x_vals[p[0]].add(p[1])
			y_vals[p[1]].add(p[0])
		min_area = 40000 * 40000 + 1
		for (x, y_coords) in list(x_vals.items()):
			if len(y_coords) == 1:
				continue
			y_list = list(y_coords)
			for (i, y_1) in enumerate(y_list):
				for (j, y_2) in enumerate(y_list[i + 1:]):
					common_x_2 = y_vals[y_1].intersection(y_vals[y_2])
					common_x_2.remove(x)
					for x_2 in list(common_x_2):
						min_area = min(min_area, abs(x_2 - x) * abs(y_2 - y_1))
		if min_area == 40000 * 40000 + 1:
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set([tuple(x) for x in points])
		min_size = float('inf')
		n = len(points)
		for i in range(n):
			(x1, y1) = points[i]
			for j in range(i + 1, n):
				(x2, y2) = points[j]
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in point_set and (x2, y1) in point_set:
					size = (y2 - y1) * (x2 - x1)
					min_size = min(min_size, abs(size))
					continue
		if min_size == float('inf'):
			return 0
		return min_size


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		m = set()
		for point in points:
			m.add(tuple(point))
		res = 1073741823
		for i in range(len(points)):
			(x1, y1) = points[i]
			for j in range(i + 1, len(points)):
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2:
					if (x1, y2) in m and (x2, y1) in m:
						res = min(res, abs((y1 - y2) * (x1 - x2)))
		res = 0 if res == 1073741823 else res
		return res


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		mapper = defaultdict(set)
		for point in points:
			mapper[point[1]].add(point[0])
		result = float('inf')
		for (y1, x_values1) in list(mapper.items()):
			for (y2, x_values2) in list(mapper.items()):
				if y1 == y2:
					continue
				intersect = x_values1.intersection(x_values2)
				if len(intersect) < 2:
					continue
				x_min_diff = self.min_diff(list(intersect))
				temp = x_min_diff * abs(y1 - y2)
				if temp < result:
					result = temp
		return result if result != float('inf') else 0

	def min_diff(self, given: list) -> int:
		result = float('inf')
		for i in range(len(given)):
			for j in range(i + 1, len(given)):
				diff = abs(given[i] - given[j])
				if diff < result:
					result = diff
		return result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set(map(tuple, points))
		min_area = float('inf')
		for (i, p1) in enumerate(points):
			for j in range(i):
				p2 = points[j]
				potential_area = abs(p1[0] - p2[0]) * abs(p1[1] - p2[1])
				if potential_area == 0 or potential_area > min_area:
					continue
				if (p1[0], p2[1]) in point_set and (p2[0], p1[1]) in point_set:
					min_area = min(potential_area, min_area)
		return 0 if min_area == float('inf') else min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = set(((r, c) for (r, c) in points))
		m = 2 ** 32
		for i in range(len(points)):
			(x1, y1) = points[i]
			for j in range(i, len(points)):
				(x2, y2) = points[j]
				if x2 == x1 or y2 == y1:
					continue
				if (x2, y1) not in points_set:
					continue
				if (x1, y2) not in points_set:
					continue
				area = abs(x1 - x2) * abs(y1 - y2)
				m = min(m, area)
		if m == 2 ** 32:
			return 0
		else:
			return m


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		st = set()
		for (x, y) in points:
			st.add((x, y))
		minarea = float('Inf')
		for (i, p1) in enumerate(points):
			for p2 in points[:i]:
				(x1, y1) = p1
				(x2, y2) = p2
				if x1 != x2 and y1 != y2 and ((x1, y2) in st) and ((x2, y1) in st):
					minarea = min(minarea, abs(x1 - x2) * abs(y1 - y2))
		return minarea if minarea < float('Inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = sorted(points, key=lambda x: (x[0], x[1]))
		self.res = float('inf')
		self.cache = defaultdict(list)
		x_cache = defaultdict(list)
		for (x, y) in points:
			for y2 in x_cache[x]:
				if y2 < y:
					for x_other in self.cache[y, y2]:
						self.res = min(self.res, abs(x_other - x) * abs(y2 - y))
					self.cache[y, y2].append(x)
			x_cache[x].append(y)
		if self.res == float('inf'):
			self.res = 0
		return self.res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		maps = set(map(tuple, points))
		points.sort()
		n = len(points)
		result = math.inf
		for i in range(n):
			(x1, y1) = points[i]
			for j in range(i + 1, n):
				(x2, y2) = points[j]
				if x2 == x1 or y1 == y2:
					continue
				if (x1, y2) in maps and (x2, y1) in maps:
					result = min(result, (x2 - x1) * abs(y2 - y1))
		return 0 if math.isinf(result) else result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = sys.maxsize
		diag = collections.defaultdict(set)
		for (i, j) in points:
			diag[i].add(j)
		for i in range(len(points)):
			(a1, a2) = points[i]
			for j in range(len(points)):
				(b1, b2) = points[j]
				if not (b1 > a1 and b2 > a2):
					continue
				if b2 in diag[a1] and a2 in diag[b1]:
					res = min(res, abs(a1 - b1) * abs(a2 - b2))
		return res if res != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:

		def intersection(lst1, lst2):
			return list(set(lst1) & set(lst2))
		col = defaultdict(list)
		ans = float('inf')
		for point in points:
			col[point[0]].append(point[1])
		cols = list(col.keys())
		for i1 in range(len(cols)):
			for i2 in range(i1 + 1, len(cols)):
				col1 = cols[i1]
				col2 = cols[i2]
				il = sorted(intersection(col[col1], col[col2]))
				for i in range(1, len(il)):
					ans = min(ans, (il[i] - il[i - 1]) * abs(col2 - col1))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		area = float(inf)
		dt = set()
		for (x, y) in points:
			dt.add((x, y))
		for i in range(len(points)):
			(x, y) = points[i]
			for j in range(i + 1, len(points)):
				(h, v) = points[j]
				if h == x or v == y:
					continue
				if (x, v) in dt and (h, y) in dt:
					area = min(area, abs(y - v) * abs(h - x))
		return area if area != float('inf') else 0


import itertools

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		ybucket = defaultdict(list)
		for (x, y) in points:
			ybucket[y].append(x)
		for (k, v) in ybucket.items():
			if len(v) >= 2:
				ybucket[k] = sorted(v)
		ys = [k for k in ybucket.keys() if len(ybucket[k]) >= 2]
		ans = float('inf')
		for (y1, y2) in itertools.combinations(ys, 2):
			row1 = set(ybucket[y1])
			row2 = ybucket[y2]
			dy = abs(y2 - y1)
			xlast = None
			for x in row2:
				if x in row1:
					if xlast is not None:
						ans = min(ans, abs(x - xlast) * dy)
					xlast = x
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xs = collections.defaultdict(set)
		ys = collections.defaultdict(set)
		for point in points:
			(x, y) = (point[0], point[1])
			xs[x].add(y)
			ys[y].add(x)
		area = 40000 ** 2 + 1
		for x in xs:
			for (y1, y2) in itertools.product(xs[x], xs[x]):
				if y1 <= y2:
					continue
				A = set((xx for xx in ys[y1] & ys[y2] if xx < x))
				if len(A) > 0:
					area = min(area, (y1 - y2) * (x - max(A)))
		return 0 if area == 40000 ** 2 + 1 else area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ptmap = {}
		min_area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in ptmap:
				if (x1, y2) in ptmap and (x2, y1) in ptmap:
					area = abs(x2 - x1) * abs(y2 - y1)
					min_area = min(area, min_area)
			ptmap[x1, y1] = (x1, y1)
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointrec = dict()
		for (x, y) in points:
			if not x in pointrec:
				pointrec[x] = dict()
			pointrec[x][y] = 1
		area = 16 * 10 ** 8
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				a = abs((points[i][0] - points[j][0]) * (points[i][1] - points[j][1]))
				if a == 0:
					continue
				if a < area and points[j][1] in pointrec[points[i][0]] and (points[i][1] in pointrec[points[j][0]]):
					area = a
		if area == 16 * 10 ** 8:
			area = 0
		return area


from collections import defaultdict
from itertools import combinations

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		mPoints = set(((x, y) for (x, y) in points))
		area = float('inf')
		for ((x1, y1), (x2, y2)) in combinations(points, 2):
			if x1 != x2 and y1 != y2 and ((x1, y2) in mPoints) and ((x2, y1) in mPoints):
				area = min(area, abs(x1 - x2) * abs(y1 - y2))
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xd = collections.defaultdict(set)
		for p in points:
			xd[p[0]].add(p[1])
		yd = collections.defaultdict(list)
		for (x, v) in list(xd.items()):
			if len(v) < 2:
				continue
			ys = list(v)
			for i in range(len(ys)):
				for j in range(i + 1, len(ys)):
					(miny, maxy) = (min(ys[i], ys[j]), max(ys[i], ys[j]))
					yd[miny, maxy].append(x)
		res = float('inf')
		for (ypair, xlist) in list(yd.items()):
			if len(xlist) < 2:
				continue
			xlist = sorted(xlist)
			h = ypair[1] - ypair[0]
			for i in range(len(xlist) - 1):
				res = min(res, h * (xlist[i + 1] - xlist[i]))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		d = collections.defaultdict(set)
		for i in range(len(points)):
			(x0, y0) = points[i]
			for j in range(i + 1, len(points)):
				(x1, y1) = points[j]
				if x0 == x1:
					d[x0].add(tuple(sorted([y0, y1])))
		seen = set()
		minA = float('inf')
		for (x0, lines0) in d.items():
			seen.add(x0)
			for (x1, lines1) in d.items():
				if x1 not in seen:
					for l in lines0:
						if l in lines1:
							minA = min(minA, abs(x0 - x1) * (l[1] - l[0]))
		return minA if minA < float('inf') else 0


from collections import defaultdict
from bisect import insort

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		if len(set(X[0])) == 1 or len(set(X[1])) == 1:
			return 0
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			insort(columns[r], c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in columns.items():
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						ans = min(ans, (r - lastc[c1, c2]) * (c2 - c1))
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x_to_points = defaultdict(lambda : [])
		y_to_points = defaultdict(lambda : set())
		for [x, y] in points:
			x_to_points[x].append((x, y))
			y_to_points[y].add((x, y))
		min_rect = float('inf')
		for x in sorted(x_to_points.keys()):
			xpoints = x_to_points[x]
			if len(xpoints) < 2:
				continue
			for x1_index in range(len(xpoints)):
				for x2_index in range(x1_index + 1, len(xpoints)):
					(x1, y1) = xpoints[x1_index]
					(x2, y2) = xpoints[x2_index]
					for (x3, y3) in y_to_points[y1]:
						if x3 == x2:
							continue
						if (x3, y2) in y_to_points[y2]:
							min_rect = min(min_rect, abs(y2 - y1) * abs(x3 - x2))
		return 0 if min_rect == float('inf') else min_rect


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = inf = float('inf')
		points_set = set((tuple(i) for i in points))
		points = list(points_set)
		n = len(points)
		for i in range(n):
			for j in range(i + 1, n):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2 and ((x1, y2) in points_set) and ((x2, y1) in points_set):
					res = min(res, abs((x2 - x1) * (y2 - y1)))
		return res if res != inf else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		dctyx = defaultdict(set)
		dctxy = defaultdict(set)
		xlist = []
		ylist = []
		for (x, y) in points:
			dctyx[y].add(x)
			dctxy[x].add(y)
		ans = inf
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if not (x1 == x2 or y1 == y2):
					if y2 in dctxy[x1] and x2 in dctyx[y1]:
						ans = min(ans, abs(x1 - x2) * abs(y1 - y2))
		return ans if ans != inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		x_coord = collections.defaultdict(list)
		points.sort(key=lambda x: (x[0], x[1]))
		min_area = float('inf')
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 == x2:
					if (y1, y2) in x_coord:
						x_other = x_coord[y1, y2][-1]
						min_area = min(min_area, (y2 - y1) * (x1 - x_other))
					x_coord[y1, y2].append(x1)
		return min_area if min_area != float('inf') else 0


from itertools import combinations

class Solution:

	def minAreaRect(self, points) -> int:
		point_x = {}
		point_y = {}
		result = float('inf')
		for i in points:
			if point_x.get(i[0]):
				point_x[i[0]].add(i[1])
			else:
				point_x[i[0]] = set([i[1]])
			if point_y.get(i[1]):
				point_y[i[1]].add(i[0])
			else:
				point_y[i[1]] = set([i[0]])
		for i in point_x:
			if len(point_x[i]) < 2:
				continue
			for (y1, y2) in combinations(point_x[i], 2):
				inter = sorted(point_y[y1].intersection(point_y[y2]))
				if len(inter) >= 2:
					result = min(min([inter[j] - inter[j - 1] for j in range(1, len(inter))]) * abs(y1 - y2), result)
		if result == float('inf'):
			result = 0
		return result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		coord = {(x, y) for (x, y) in points}
		n = len(points)
		min_area = sys.maxsize
		for i in range(n):
			for j in range(i + 1, n):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in coord and (x2, y1) in coord:
					min_area = min(min_area, abs((x1 - x2) * (y1 - y2)))
		return min_area if min_area != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		s = set()
		for (a, b) in points:
			s.add((a, b))
		n = len(points)
		res = float('inf')
		for i in range(n):
			for j in range(i + 1, n):
				(a, b) = points[i]
				(c, d) = points[j]
				if a != c and b != d:
					if (a, d) in s and (c, b) in s:
						res = min(res, abs((a - c) * (b - d)))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		counter = Counter(list(map(tuple, points)))
		if any((count >= 4 for count in list(counter.values()))):
			return 0
		points = list(counter)
		result = float('inf')
		for (i, (x, y)) in enumerate(points):
			for j in range(i + 1, len(points)):
				(x_, y_) = points[j]
				if x != x_ and y != y_:
					if (x, y_) in counter and (x_, y) in counter:
						result = min(result, abs((x_ - x) * (y_ - y)))
						if not result:
							break
		return 0 if result == float('inf') else result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		points_table = set()
		for (x, y) in points:
			points_table.add((x, y))
		min_area = float('inf')
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2:
					if (x1, y2) in points_table and (x2, y1) in points_table:
						min_area = min(min_area, abs(x1 - x2) * abs(y1 - y2))
		return 0 if min_area == float('inf') else min_area


MAX_VAL = 10 ** 9 + 7

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = set()
		for (x, y) in points:
			points_set.add((x, y))
		n = len(points)
		min_area = MAX_VAL
		for i in range(n - 1):
			for j in range(i + 1, n):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2 and ((x2, y1) in points_set) and ((x1, y2) in points_set):
					curr_area = abs((x1 - x2) * (y1 - y2))
					min_area = min(min_area, curr_area)
		return 0 if min_area == MAX_VAL else min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointset = set([(x, y) for (x, y) in points])
		minArea = math.inf
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2 and ((x1, y2) in pointset) and ((x2, y1) in pointset):
					area = abs((x1 - x2) * (y1 - y2))
					minArea = min(area, minArea)
		return minArea if minArea < math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		import math
		from collections import defaultdict
		row_m = defaultdict(set)
		rows = set()
		for (x, y) in points:
			row_m[x].add(y)
			rows.add(x)
		rows = sorted(rows)
		l = len(rows)
		sol = math.inf
		for i in range(l):
			x1 = rows[i]
			for j in range(i + 1, l):
				x2 = rows[j]
				row1 = row_m[x1]
				row2 = row_m[x2]
				intersect = sorted(set(row1) & set(row2))
				if len(intersect) < 1:
					continue
				smallest = math.inf
				for (i, point) in enumerate(intersect[1:], start=1):
					smallest = min(smallest, point - intersect[i - 1])
				sol = min(sol, smallest * (x2 - x1))
		if sol is math.inf:
			return 0
		return sol


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		nx = len(set((x for (x, y) in points)))
		ny = len(set((y for (x, y) in points)))
		if nx == n or ny == n:
			return 0
		res = 2 ** 31
		s = {(p[0], p[1]) for p in points}
		for (i, p1) in enumerate(points):
			for (j, p2) in enumerate(points[i + 1:]):
				if p1[0] != p2[0] and p1[1] != p2[1]:
					if (p1[0], p2[1]) in s and (p2[0], p1[1]) in s:
						res = min(res, abs(p1[1] - p2[1]) * abs(p1[0] - p2[0]))
		res = res if res < 2 ** 31 else 0
		return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		rows = defaultdict(set)
		cols = defaultdict(set)
		for (i, point) in enumerate(points):
			rows[point[0]].add(tuple(point))
			cols[point[1]].add(tuple(point))
		minArea = 99999999999
		for point in points:
			rowPoints = rows[point[0]]
			colPoints = cols[point[1]]
			for iP in rowPoints:
				for jP in colPoints:
					if iP[1] > point[1] and jP[0] > point[0] and ((jP[0], iP[1]) in rows[jP[0]]):
						minArea = min(minArea, (iP[1] - point[1]) * (jP[0] - point[0]))
		if minArea == 99999999999:
			return 0
		return minArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set()
		area = 0
		for (i1, j1) in points:
			for (i2, j2) in points:
				if i1 != i2 and j1 != j2:
					if (i1, j2) in point_set and (i2, j1) in point_set:
						if area == 0:
							area = abs(i1 - i2) * abs(j1 - j2)
						else:
							area = min(area, abs(i1 - i2) * abs(j1 - j2))
			point_set.add((i1, j1))
		return area


from collections import defaultdict
from bisect import insort

class Solution:

	def minAreaRect(self, points):
		(setr, setc) = (set(), set())
		for (r, c) in points:
			setr.add(r)
			setc.add(c)
		if len(points) in (len(setr), len(setc)):
			return 0
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			insort(columns[r], c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in list(columns.items()):
			for (j, y2) in enumerate(cols):
				for (i, y1) in enumerate(cols[:j]):
					if (y1, y2) in lastc:
						ans = min(ans, (r - lastc[y1, y2]) * (y2 - y1))
					lastc[y1, y2] = r
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		data = set()
		res = 2 ** 31 - 1
		for (x1, y1) in points:
			for (x2, y2) in data:
				if (x1, y2) in data and (x2, y1) in data:
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
			data.add((x1, y1))
		return res if res < 2 ** 31 - 1 else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xAxis = {}
		yAxis = {}
		minArea = None
		for point in points:
			if xAxis.get(point[0]):
				xAxis[point[0]].append(point[1])
			else:
				xAxis[point[0]] = [point[1]]
			if yAxis.get(point[1]):
				yAxis[point[1]].append(point[0])
			else:
				yAxis[point[1]] = [point[0]]
		for point in points:
			topLeft = xAxis[point[0]]
			bottomRight = yAxis[point[1]]
			for tlPoint in topLeft:
				if tlPoint == point[1]:
					continue
				possibleTopRight = yAxis[tlPoint]
				topRight = [value for value in possibleTopRight if value in bottomRight and value != point[0]]
				for trPoint in topRight:
					area = abs((trPoint - point[0]) * (tlPoint - point[1]))
					if area != 0 and (minArea == None or area < minArea):
						minArea = area
			xAxis[point[0]].remove(point[1])
			yAxis[point[1]].remove(point[0])
		return 0 if minArea == None else minArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xys = set()
		for point in points:
			xys.add((point[0], point[1]))
		sq_min = float('inf')
		for (i, pointi) in enumerate(points):
			(xi, yi) = (pointi[0], pointi[1])
			for j in range(i + 1, len(points)):
				(xj, yj) = (points[j][0], points[j][1])
				if xi != xj and yi != yj and ((xi, yj) in xys) and ((xj, yi) in xys):
					sq_min = min(sq_min, abs((xi - xj) * (yi - yj)))
		return sq_min if sq_min != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		s = set([(x, y) for (x, y) in points])
		res = float('inf')
		for (i, point1) in enumerate(points):
			for j in range(i):
				point2 = points[j]
				(x1, y1) = point1
				(x2, y2) = point2
				if x1 != x2 and y1 != y2 and ((x1, y2) in s) and ((x2, y1) in s):
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointsSet = set([(x, y) for (x, y) in points])
		points = list(pointsSet)
		numberOfPoints = len(points)
		minimumArea = float('inf')
		for i in range(numberOfPoints):
			for j in range(i + 1, numberOfPoints):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2 and ((x1, y2) in pointsSet) and ((x2, y1) in pointsSet):
					minimumArea = min(minimumArea, abs(x2 - x1) * abs(y2 - y1))
		return 0 if minimumArea == float('inf') else minimumArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointSet = set()
		for (dx, dy) in points:
			pointSet.add((dx, dy))
		minArea = float('inf')
		for i in range(len(points)):
			(x1, y1) = (points[i][0], points[i][1])
			for j in range(i + 1, len(points)):
				(x2, y2) = (points[j][0], points[j][1])
				if x1 != x2 and y1 != y2:
					if (x2, y1) in pointSet and (x1, y2) in pointSet:
						minArea = min(minArea, abs(x2 - x1) * abs(y2 - y1))
		return minArea if minArea < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = float('inf')
		pointSet = set([tuple(p) for p in points])
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in pointSet and (x2, y1) in pointSet:
					res = min(res, abs(x1 - x2) * abs(y1 - y2))
		if res == float('inf'):
			return 0
		return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		nx = len(set((x for (x, y) in points)))
		ny = len(set((y for (x, y) in points)))
		if nx == n or ny == n:
			return 0
		lastx = {}
		everyx = collections.defaultdict(list)
		min_area = math.inf
		for (x, y) in points:
			everyx[x].append(y)
		for x in sorted(everyx):
			everyy = sorted(everyx[x])
			for (i, y1) in enumerate(everyy):
				for j in range(i):
					y2 = everyy[j]
					if (y1, y2) in lastx:
						area = abs(y2 - y1) * abs(x - lastx[y1, y2])
						min_area = min(area, min_area)
					lastx[y1, y2] = x
		return min_area if min_area < math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points or len(points) <= 3:
			return 0
		visited = set()
		res = float('Inf')
		for (x1, y1) in points:
			for (x2, y2) in visited:
				if (x1, y2) in visited and (x2, y1) in visited:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area and area <= res:
						res = area
			visited.add((x1, y1))
		return res if res != float('Inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set()
		for (x, y) in points:
			point_set.add((x, y))
		min_area = float('inf')
		for (i, (x1, y1)) in enumerate(points):
			for (x2, y2) in points[i + 1:]:
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in point_set and (x2, y1) in point_set:
					min_area = min(min_area, abs((x1 - x2) * (y1 - y2)))
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_dict = {}
		point_list = []
		for i in points:
			point_dict[i[0], i[1]] = 1
			point_list.append((i[0], i[1]))
		print(point_dict)
		print(point_list)
		ans = math.inf
		for i in range(0, len(points)):
			for j in range(i, len(points)):
				(ix, iy) = point_list[i]
				(jx, jy) = point_list[j]
				if ix == jx or iy == jy:
					continue
				if (ix, jy) in point_dict and (jx, iy) in point_dict:
					ans = min(ans, abs(ix - jx) * abs(iy - jy))
		if ans == math.inf:
			return 0
		return ans


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = {(x, y) for (x, y) in points}
		min_area = float('inf')
		for (x1, y1) in points:
			for (x2, y2) in points:
				if x1 == x2 or y1 == y2:
					continue
				(x3, y3, x4, y4) = (x1, y2, x2, y1)
				theoretical_area = abs((x1 - x2) * (y1 - y2))
				if theoretical_area > min_area:
					continue
				if (x3, y3) in points and (x4, y4) in points:
					min_area = min(min_area, abs((x1 - x2) * (y1 - y2)))
		if min_area == float('inf'):
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		coords = {}
		for (x, y) in points:
			if x not in coords:
				coords[x] = {}
			coords[x][y] = True
		area = None
		for x1 in coords:
			for y1 in coords[x1]:
				for y2 in coords[x1]:
					if y1 == y2:
						continue
					for x2 in coords:
						if x1 == x2:
							continue
						if y1 in coords[x2] and y2 in coords[x2]:
							current = abs(x1 - x2) * abs(y1 - y2)
							if area == None or current < area:
								area = current
		if area == None:
			return 0
		return area


import math
import itertools
import collections

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x_index = defaultdict(set)
		y_index = defaultdict(set)
		for (x, y) in points:
			x_index[x].add(y)
			y_index[y].add(x)
		rects = []
		for (p1, p2) in itertools.combinations(points, 2):
			(x1, y1) = p1
			(x2, y2) = p2
			if x1 == x2 or y1 == y2:
				continue
			if y1 in x_index[x2] and x1 in y_index[y2]:
				rects.append([p1, p2])
		if len(rects) == 0:
			return 0
		ret = math.inf
		for ((x1, y1), (x2, y2)) in rects:
			area = abs((x1 - x2) * (y1 - y2))
			if area < ret:
				ret = area
		return ret


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = set(map(tuple, points))
		ans = float('inf')
		for (j, p2) in enumerate(points):
			for i in range(j):
				p1 = points[i]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set([tuple(p) for p in points])
		min_area = float('inf')
		for (idx, p1) in enumerate(points):
			for idx2 in range(idx, len(points)):
				p2 = points[idx2]
				if p1[0] != p2[0] and p1[1] != p2[1]:
					p3 = (p1[0], p2[1])
					p4 = (p2[0], p1[1])
					if p3 in point_set and p4 in point_set:
						dx = abs(p1[0] - p2[0])
						dy = abs(p1[1] - p2[1])
						area = dx * dy
						if area < min_area:
							min_area = area
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		min_area = 999999999999999999
		points = [(l[0], l[1]) for l in points]
		s_points = set(points)
		for p1 in points:
			for p2 in points:
				(x1, y1) = p1
				(x2, y2) = p2
				if x1 == x2 or y1 == y2:
					continue
				area = abs(x2 - x1) * abs(y2 - y1)
				if area < min_area:
					if (x1, y2) in s_points and (x2, y1) in s_points:
						min_area = area
		if min_area is 999999999999999999:
			return 0
		return min_area


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		p_set = set(map(tuple, points))
		res = float('inf')
		for (j, p2) in enumerate(points):
			for i in range(j):
				p1 = points[i]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in p_set) and ((p2[0], p1[1]) in p_set):
					area = abs(p1[0] - p2[0]) * abs(p1[1] - p2[1])
					res = min(area, res)
		return 0 if res == float('inf') else res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		from collections import defaultdict
		(x_set, y_set) = (set(), set())
		for (x, y) in points:
			x_set.add(x)
			y_set.add(y)
		if len(x_set) == len(points) or len(y_set) == len(points):
			return 0
		columns = defaultdict(list)
		for (x, y) in points:
			columns[x].append(y)
		visited = {}
		res = float('inf')
		for col in sorted(columns):
			num_y = columns[col]
			num_y.sort()
			for i in range(len(num_y)):
				for j in range(i):
					y1 = num_y[i]
					y2 = num_y[j]
					if (y1, y2) in visited:
						col_prev = visited[y1, y2]
						area = (y1 - y2) * (col - col_prev)
						res = min(res, area)
					visited[y1, y2] = col
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointset = {tuple(i) for i in points}
		ans = float('inf')
		area = lambda x, y: abs((x[0] - y[0]) * (x[1] - y[1]))
		for (A, B) in combinations(points, 2):
			if A[0] == B[0] or A[1] == B[1]:
				continue
			if (A[1] - B[1]) // (A[0] - B[0]) >= 0:
				continue
			C = (A[0], B[1])
			D = (B[0], A[1])
			if C in pointset and D in pointset:
				ans = min(ans, area(A, B))
		return ans if ans != float('inf') else 0


import sys

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = set([(x, y) for (x, y) in points])
		mini = sys.maxsize
		for (i, p1) in enumerate(points):
			for j in range(i):
				p2 = points[j]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					mini = min(mini, abs((p1[1] - p2[1]) * (p1[0] - p2[0])))
		return mini if mini != sys.maxsize else 0


class Solution:

	def minAreaRectangularHull(self, points: List[List[int]]) -> int:
		area = 0
		if points:
			(minx, miny) = points[0]
			(maxx, maxy) = points[0]
			for (x, y) in points:
				minx = min(minx, x)
				miny = min(miny, y)
				maxx = max(maxx, x)
				maxy = max(maxy, y)
			area = (maxx - minx) * (maxy - miny)
		return area

	def minAreaRect(self, points):
		S = set(map(tuple, points))
		ans = float('inf')
		for (j, p2) in enumerate(points):
			for i in range(j):
				p1 = points[i]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return ans if ans < float('inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		(setr, setc) = (set(), set())
		for (r, c) in points:
			setr.add(r)
			setc.add(c)
		if len(points) in (len(setr), len(setc)):
			return 0
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for r in sorted(columns):
			cols = sorted(columns[r])
			for (j, y2) in enumerate(cols):
				for (i, y1) in enumerate(cols[:j]):
					if (y1, y2) in lastc:
						ans = min(ans, (r - lastc[y1, y2]) * (y2 - y1))
					lastc[y1, y2] = r
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		S = set(map(tuple, points))
		ans = float('inf')
		for (j, p2) in enumerate(points):
			for (i, p1) in enumerate(points[:j]):
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		xD = collections.defaultdict(list)
		for (x, y) in points:
			xD[x].append(y)
		sol = math.inf
		lastSeen = collections.defaultdict(int)
		for x in sorted(xD.keys()):
			for i1 in range(len(xD[x])):
				for i2 in range(i1 + 1, len(xD[x])):
					(pair1, pair2, diff) = ((xD[x][i1], xD[x][i2]), (xD[x][i2], xD[x][i1]), abs(xD[x][i1] - xD[x][i2]))
					if pair1 in lastSeen or pair2 in lastSeen:
						sol = min(diff * (x - lastSeen[pair1]), sol)
					(lastSeen[pair1], lastSeen[pair2]) = (x, x)
		return sol if sol != math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = 2 ** 31
		s = {(p[0], p[1]) for p in points}
		for (i, p1) in enumerate(points):
			for (j, p2) in enumerate(points[i + 1:]):
				if p1[0] != p2[0] and p1[1] != p2[1]:
					if (p1[0], p2[1]) in s and (p2[0], p1[1]) in s:
						res = min(res, abs(p1[1] - p2[1]) * abs(p1[0] - p2[0]))
		res = res if res < 2 ** 31 else 0
		return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set()
		points.sort()
		for point in points:
			point_set.add((point[0], point[1]))

		def getArea(point1: List[int], point2: List[int]) -> int:
			if point2[0] <= point1[0] or point2[1] <= point1[1]:
				return 0
			if (point1[0], point2[1]) in point_set and (point2[0], point1[1]) in point_set:
				return (point2[0] - point1[0]) * (point2[1] - point1[1])
			return 0
		min_area = math.inf
		N = len(points)
		for i in range(N):
			start_point = points[i]
			for j in range(i + 1, N):
				area = getArea(start_point, points[j])
				if area > 0:
					min_area = min(min_area, area)
		return min_area if min_area != math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		horizontal = collections.defaultdict(set)
		vertical = collections.defaultdict(set)
		for (x, y) in points:
			horizontal[y].add(x)
			vertical[x].add(y)
		xlist = [x for x in vertical if len(vertical[x]) > 1]
		ans = float('inf')
		for i in range(len(xlist) - 1):
			x1 = xlist[i]
			for j in range(i + 1, len(xlist)):
				x2 = xlist[j]
				cand = []
				for y in vertical[x1]:
					if y in vertical[x2]:
						cand.append(y)
				if len(cand) >= 2:
					cand.sort()
					for i in range(len(cand) - 1):
						ans = min(ans, abs(x2 - x1) * (cand[i + 1] - cand[i]))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points):
		S = set(map(tuple, points))
		ans = float('inf')
		for (index_j, p2) in enumerate(points):
			for index_i in range(index_j):
				p1 = points[index_i]
				if p1[0] != p2[0] and p1[1] != p2[1]:
					if (p1[0], p2[1]) in S and (p2[0], p1[1]) in S:
						ans = min(ans, abs((p1[0] - p2[0]) * (p1[1] - p2[1])))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		point_set = set()
		(x_map, y_map) = (defaultdict(set), defaultdict(set))
		for (x, y) in points:
			point_set.add((x, y))
			x_map[x].add((x, y))
			y_map[y].add((x, y))
		min_rec = math.inf

		def dfs(points: list):
			nonlocal x_map, y_map, point_set, min_rec
			if len(points) not in (1, 2, 3):
				return
			if len(points) == 1:
				(x, y) = points[0]
				for point in x_map[x]:
					if point[1] < y:
						points.append(point)
						dfs(points)
						points.pop()
			elif len(points) == 2:
				(x, y) = points[0]
				for point in y_map[y]:
					if point[0] > x:
						points.append(point)
						dfs(points)
						points.pop()
			else:
				(x2, y1) = (points[2][0], points[1][1])
				if (x2, y1) in point_set:
					(x1, y2) = (points[1][0], points[2][1])
					min_rec = min(min_rec, (x2 - x1) * (y2 - y1))
		for point in point_set:
			dfs([point])
		if min_rec != math.inf:
			return min_rec
		else:
			return 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = set(map(tuple, points))
		min_area = float('inf')
		for (idx, p2) in enumerate(points):
			for i in range(idx):
				p1 = points[i]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in points_set) and ((p2[0], p1[1]) in points_set):
					area = abs((p2[0] - p1[0]) * (p2[1] - p1[1]))
					min_area = min(min_area, area)
		return min_area if min_area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = sorted(points)
		points_set = set([tuple(p) for p in points])
		min_area = 999999999999
		has_rectangle = False
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				x1 = points[i][0]
				y1 = points[i][1]
				x2 = points[j][0]
				y2 = points[j][1]
				if x1 == x2:
					continue
				if y1 == y2:
					continue
				if (x1, y2) not in points_set:
					continue
				if (x2, y1) not in points_set:
					continue
				area = abs((x1 - x2) * (y1 - y2))
				has_rectangle = True
				if area < min_area:
					min_area = area
		if not has_rectangle:
			return 0
		else:
			return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = set(map(tuple, points))
		ans = float('inf')
		for (j, p2) in enumerate(points):
			for i in range(j):
				p1 = points[i]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return ans if ans < float('inf') else 0
		columns = collections.defaultdict(list)
		for (x, y) in points:
			columns[x].append(y)
		lastx = {}
		ans = float('inf')
		for x in sorted(columns):
			column = columns[x]
			column.sort()
			for (j, y2) in enumerate(column):
				for i in range(j):
					y1 = column[i]
					if (y1, y2) in lastx:
						ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
					lastx[y1, y2] = x
		return ans if ans < float('inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ss = set([tuple(ele) for ele in points])
		ans = float('inf')
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if (x2, y1) in ss and (x1, y2) in ss and (x1 != x2) and (y1 != y2):
					ans = min(ans, abs((x1 - x2) * (y1 - y2)))
		return 0 if ans == float('inf') else ans


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		min_area = 40000 ** 2 + 1
		m = len(points)
		points_table = set()
		for (x, y) in points:
			points_table.add((x, y))
		for i in range(m):
			for j in range(i + 1, m):
				a = points[i]
				b = points[j]
				if a[0] != b[0] and a[1] != b[1]:
					if (a[0], b[1]) in points_table and (b[0], a[1]) in points_table:
						z = abs((b[0] - a[0]) * (b[1] - a[1]))
						min_area = min(min_area, z)
		if min_area == 40000 ** 2 + 1:
			min_area = 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		d = set(map(tuple, points))
		min_square = sys.maxsize
		for (i, x) in enumerate(points):
			for j in range(i, len(points)):
				y = points[j]
				if x[0] != y[0] and x[1] != y[1] and ((x[0], y[1]) in d) and ((y[0], x[1]) in d):
					min_square = min(min_square, abs(x[0] - y[0]) * abs(x[1] - y[1]))
		return min_square if min_square != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		all_points = set([(point[0], point[1]) for point in points])
		min_area = float('inf')
		for (idx, point1) in enumerate(points):
			for (idx, point2) in enumerate(points[idx + 1:], start=idx):
				if point1[0] != point2[0] and point1[1] != point2[1] and ((point1[0], point2[1]) in all_points) and ((point2[0], point1[1]) in all_points):
					min_area = min(min_area, abs(point1[0] - point2[0]) * abs(point1[1] - point2[1]))
		return min_area if min_area != float('inf') else 0


import itertools

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		ybucket = defaultdict(list)
		for (x, y) in points:
			ybucket[y].append(x)
		for (k, v) in ybucket.items():
			if len(v) >= 2:
				ybucket[k] = sorted(v)
		ys = [k for k in ybucket.keys() if len(ybucket[k]) >= 2]
		ans = 2 ** 31 - 1
		for (y1, y2) in itertools.combinations(ys, 2):
			row1 = set(ybucket[y1])
			row2 = ybucket[y2]
			for (idx, x) in enumerate(row2):
				if x in row1:
					print(x)
					xlast = x
					idx_last = idx
					break
			else:
				continue
			dy = abs(y2 - y1)
			for x in row2[idx_last + 1:]:
				if x in row1:
					ans = min(ans, abs(x - xlast) * dy)
					xlast = x
		return ans if ans < 2 ** 31 - 1 else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ans = float('inf')
		s = {tuple(point) for point in points}
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				(p1, p2) = (points[i], points[j])
				if p1[0] == p2[0] or p1[1] == p2[1]:
					continue
				if (p1[0], p2[1]) in s and (p2[0], p1[1]) in s:
					ans = min(ans, abs(p1[0] - p2[0]) * abs(p1[1] - p2[1]))
		return ans if ans != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		hash_set = set(map(tuple, points))
		min_ = float('inf')
		for (j, p2) in enumerate(points):
			for i in range(j):
				p1 = points[i]
				(x1, y1) = (p2[0], p2[1])
				(x2, y2) = (p1[0], p1[1])
				if x1 != x2 and y1 != y2:
					if (x2, y1) in hash_set and (x1, y2) in hash_set:
						min_ = min(min_, abs(x1 - x2) * abs(y1 - y2))
		if min_ == float('inf'):
			return 0
		return min_


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = float('inf')
		dic = collections.defaultdict(set)
		for p in points:
			dic[p[0]].add(p[1])
		for i in range(len(points)):
			for j in range(len(points)):
				(p1, p2) = (points[i], points[j])
				if p1[0] >= p2[0] or p1[1] >= p2[1]:
					continue
				if p1[1] in dic[p2[0]] and p2[1] in dic[p1[0]]:
					res = min(res, (p2[0] - p1[0]) * (p2[1] - p1[1]))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		area = float('inf')
		points_set = {tuple(p) for p in points}
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 != x2 and y1 != y2:
					if (x2, y1) in points_set and (x1, y2) in points_set:
						area = min(abs(y2 - y1) * abs(x2 - x1), area)
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		_set = {(x, y) for (x, y) in points}
		res = math.inf
		for (p1, p2) in combinations(points, 2):
			arr = [p1, p2]
			arr.sort()
			((x1, y1), (x2, y2)) = arr
			(l, w) = (y2 - y1, x2 - x1)
			if l > 0 and w > 0 and ((x1, y1 + l) in _set) and ((x1 + w, y1) in _set):
				res = min(res, l * w)
		return 0 if math.isinf(res) else res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointSet = set()
		for (x, y) in points:
			pointSet.add((x, y))
		length = len(points)
		minArea = float('inf')
		for i in range(length):
			for j in range(i, length):
				p1 = points[i]
				p2 = points[j]
				if p1[0] != p2[0] and p1[1] != p2[1]:
					if (p1[0], p2[1]) in pointSet and (p2[0], p1[1]) in pointSet:
						minArea = min(minArea, abs(p1[0] - p2[0]) * abs(p1[1] - p2[1]))
		if minArea == float('inf'):
			return 0
		return minArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		n = len(points)
		result = math.inf
		seen = set()
		for i in range(n):
			(x1, y1) = points[i]
			for j in range(i + 1, n):
				(x2, y2) = points[j]
				if x2 == x1:
					continue
				a = (x1, y2, x2, y1)
				if a in seen:
					result = min(result, (x2 - x1) * abs(y2 - y1))
				seen.add((x1, y1, x2, y2))
		return 0 if math.isinf(result) else result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		ans = float('inf')
		seen = set(map(tuple, points))
		points.sort()
		for i in range(len(points)):
			for j in range(i):
				(x1, y1) = (points[i][0], points[i][1])
				(x2, y2) = (points[j][0], points[j][1])
				if x1 != x2 and y1 != y2 and ((x1, y2) in seen) and ((x2, y1) in seen):
					ans = min(ans, (x1 - x2) * abs(y2 - y1))
		return ans if ans != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		s = set()
		for point in points:
			x = point[0]
			y = point[1]
			s.add((x, y))
		res = float('inf')
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				x1 = points[i][0]
				y1 = points[i][1]
				x2 = points[j][0]
				y2 = points[j][1]
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in s and (x2, y1) in s:
					res = min(res, abs((y2 - y1) * (x2 - x1)))
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		p_set = set([(x, y) for (x, y) in points])
		res = float('inf')
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				p1 = points[i]
				p2 = points[j]
				if p1[0] == p2[0] or p1[1] == p2[1]:
					continue
				up = (p1[0], p2[1])
				left = (p2[0], p1[1])
				if up in p_set and left in p_set:
					area = abs(p1[0] - p2[0]) * abs(p1[1] - p2[1])
					res = min(res, area)
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointset = {tuple(i) for i in points}
		ans = float('inf')
		area = lambda x, y: abs((x[0] - y[0]) * (x[1] - y[1]))
		for (i, A) in enumerate(points):
			for j in range(i):
				B = points[j]
				if A[0] == B[0] or A[1] == B[1]:
					continue
				if (A[0], B[1]) in pointset and (B[0], A[1]) in pointset:
					ans = min(ans, area(A, B))
		return ans if ans != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		base_x_to_y = collections.defaultdict(dict)
		y_for_base_x = []
		base_x = -1
		min_area = float('inf')
		for (x, y) in sorted(points):
			if x != base_x:
				base_x = x
				y_for_base_x = []
			for prev_base_x in y_for_base_x:
				if y in base_x_to_y[prev_base_x]:
					w = x - base_x_to_y[prev_base_x][y]
					h = y - prev_base_x
					area = w * h
					min_area = min(min_area, area)
				base_x_to_y[prev_base_x][y] = x
			y_for_base_x.append(y)
		return min_area if min_area < float('inf') else 0


class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points = [Point(x, y) for [x, y] in points]
		dic_x = collections.defaultdict(set)
		dic_y = collections.defaultdict(set)
		for p in points:
			dic_x[p.x].add(p.y)
			dic_y[p.y].add(p.x)
		area = math.inf
		for (p1, p2) in itertools.combinations(points, 2):
			if p1.x == p2.x or p1.y == p2.y:
				continue
			if p2.y in dic_x[p1.x] and p2.x in dic_y[p1.y]:
				area = min(area, abs(p2.x - p1.x) * abs(p2.y - p1.y))
		return area if area != math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		minA = float('inf')
		cache = {(x, y) for (x, y) in points}
		for i in range(len(points)):
			(x1, y1) = points[i]
			for j in range(i + 1, len(points)):
				(x2, y2) = points[j]
				if (x1, y2) in cache and (x2, y1) in cache:
					area = abs(x1 - x2) * abs(y1 - y2)
					if area != 0:
						minA = min(minA, area)
		return minA if minA < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		point_set = {(x, y) for (x, y) in points}
		min_area = math.inf
		for i in range(n):
			(x0, y0) = points[i]
			for j in range(i + 1, n):
				(x1, y1) = points[j]
				if (x0, y1) in point_set and (x1, y0) in point_set:
					area = abs(x0 - x1) * abs(y0 - y1)
					if area > 0:
						min_area = min(min_area, area)
		return 0 if min_area == math.inf else min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		st = set()
		min_area = float('inf')
		for item in points:
			st.add((item[0], item[1]))
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				(x1, y1) = (points[i][0], points[i][1])
				(x2, y2) = (points[j][0], points[j][1])
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in st and (x2, y1) in st:
					curr_area = abs((y2 - y1) * (x2 - x1))
					min_area = min(min_area, curr_area)
		if min_area == float('inf'):
			return 0
		return min_area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = set([tuple(v) for v in points])
		min_area = None
		for (i, x1y1) in enumerate(points):
			for x2y2 in points[i:]:
				if x1y1[0] == x2y2[0] or x1y1[1] == x2y2[1]:
					continue
				x1y2 = tuple([x1y1[0], x2y2[1]])
				x2y1 = tuple([x2y2[0], x1y1[1]])
				if x1y2 in points_set and x2y1 in points_set:
					area = abs((x1y1[0] - x2y2[0]) * (x1y1[1] - x2y2[1]))
					if min_area is None or area < min_area:
						min_area = area
		return min_area if min_area else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointset = set([tuple(x) for x in points])
		res = 2 ** 32
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				p1 = points[i]
				p2 = points[j]
				if p1[0] != p2[0] and p1[1] != p2[1]:
					if (p1[0], p2[1]) in pointset and (p2[0], p1[1]) in pointset:
						res = min(res, abs(p1[0] - p2[0]) * abs(p1[1] - p2[1]))
		return res if res < 2 ** 32 else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		hashset = set()
		for (x, y) in points:
			hashset.add((x, y))
		area = float('inf')
		for i in range(len(points)):
			for j in range(len(points)):
				(x1, y1) = points[i]
				(x2, y2) = points[j]
				if x1 >= x2 or y1 >= y2:
					continue
				if (x1, y2) in hashset and (x2, y1) in hashset:
					area = min(area, (y2 - y1) * (x2 - x1))
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = {tuple(p) for p in points}
		result = float('inf')
		for j in range(len(points)):
			for i in range(j):
				p1 = points[i]
				p2 = points[j]
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in S) and ((p2[0], p1[1]) in S):
					result = min(result, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return result if result < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x = 0
		y = 1
		points_set = set()
		for point in points:
			points_set.add((point[x], point[y]))
		if len(points_set) < 4:
			return 0
		best = None
		for i in range(len(points) - 1):
			for j in range(i + 1, len(points)):
				p1 = points[i]
				p2 = points[j]
				if p1[x] == p2[x] or p1[y] == p2[y]:
					continue
				if (p1[x], p2[y]) in points_set and (p2[x], p1[y]) in points_set:
					area = abs(p2[x] - p1[x]) * abs(p2[y] - p1[y])
					best = area if best is None else min(best, area)
		return 0 if not best else best


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointsSet = set(map(tuple, points))
		pointsLength = len(points)
		minArea = float('inf')
		for i in range(pointsLength):
			for j in range(i + 1, pointsLength):
				(p1, p2) = (points[i], points[j])
				if p1[0] != p2[0] and p1[1] != p2[1] and ((p1[0], p2[1]) in pointsSet) and ((p2[0], p1[1]) in pointsSet):
					minArea = min(minArea, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return minArea if minArea < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointsSet = set((tuple(point) for point in points))
		minarea = sys.maxsize
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				x_i = points[i][0]
				y_i = points[i][1]
				x_j = points[j][0]
				y_j = points[j][1]
				if x_i != x_j and y_i != y_j and ((x_i, y_j) in pointsSet) and ((x_j, y_i) in pointsSet):
					minarea = min(minarea, abs(x_j - x_i) * abs(y_j - y_i))
		return minarea if minarea != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		min_area = sys.maxsize
		point_set = set([(p[0], p[1]) for p in points])
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				p1 = points[i]
				p2 = points[j]
				if p1[0] != p2[0] and p1[1] != p2[1]:
					p3 = (p1[0], p2[1])
					p4 = (p2[0], p1[1])
					if p3 in point_set and p4 in point_set:
						min_area = min(min_area, abs((p1[0] - p2[0]) * (p1[1] - p2[1])))
		return min_area if min_area != sys.maxsize else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = {(point[0], point[1]) for point in points}
		minArea = math.inf
		for (i, point1) in enumerate(points):
			for j in range(i):
				point2 = points[j]
				(x1, x2, y1, y2) = (point1[0], point2[0], point1[1], point2[1])
				diagPoints = x1 != x2 and y1 != y2
				if diagPoints and (x1, y2) in S and ((x2, y1) in S):
					minArea = min(minArea, abs(x1 - x2) * abs(y1 - y2))
		return minArea if minArea != math.inf else 0


class Solution:

	def minAreaRect(self, z: List[List[int]]) -> int:
		x = defaultdict(set)
		y = defaultdict(set)
		z.sort()
		for (a, b) in z:
			x[a].add(b)
			y[b].add(a)
		ans = inf
		l = len(z)
		for k in range(l):
			(a, b) = z[k]
			for m in range(k + 1, l):
				(c, d) = z[m]
				if a < c:
					break
				for j in y[b].intersection(y[d]):
					if j != a:
						ans = min(ans, abs(b - d) * abs(a - j))
		return ans if ans != inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointSet = set(map(tuple, points))
		n = len(points)
		minArea = float('inf')
		for i in range(n - 1):
			for j in range(i + 1, n):
				(diag1, diag2) = (points[i], points[j])
				if diag2[0] == diag1[0] or diag2[1] == diag1[1]:
					continue
				if (diag2[0], diag1[1]) not in pointSet:
					continue
				if (diag1[0], diag2[1]) not in pointSet:
					continue
				minArea = min(minArea, abs(diag2[0] - diag1[0]) * abs(diag2[1] - diag1[1]))
		return minArea if minArea < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		S = set(((p[0], p[1]) for p in points))
		ans = float('inf')
		for i in range(len(points)):
			for j in range(i):
				p1 = points[i]
				p2 = points[j]
				if p1[0] == p2[0] or p1[1] == p2[1]:
					continue
				if (p1[0], p2[1]) in S and (p2[0], p1[1]) in S:
					ans = min(ans, abs(p2[0] - p1[0]) * abs(p2[1] - p1[1]))
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		x_axes = {}
		y_axes = {}
		for point in points:
			if point[0] not in x_axes:
				x_axes[point[0]] = set()
			if point[1] not in y_axes:
				y_axes[point[1]] = set()
			x_axes[point[0]].add(point[1])
			y_axes[point[1]].add(point[0])

		def findMinArea(point, x_axes, y_axes):
			possible_x = y_axes[point[1]]
			possible_y = x_axes[point[0]]
			min_area = None
			for x in possible_x:
				if x == point[0]:
					continue
				for y in possible_y:
					if y == point[1]:
						continue
					if x in y_axes[y]:
						area = abs((x - point[0]) * (y - point[1]))
						min_area = area if min_area is None else min(area, min_area)
			return min_area
		min_area = None
		for point in points:
			area = findMinArea(point, x_axes, y_axes)
			if area is not None:
				min_area = area if min_area is None else min(min_area, area)
		return min_area if min_area else 0


import sys

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		minArea = sys.maxsize
		pointSet = set()
		for point in points:
			pointSet.add((point[0], point[1]))
		for i in range(0, len(points)):
			for j in range(i + 1, len(points)):
				point1 = points[i]
				point2 = points[j]
				(x1, y1) = (point1[0], point1[1])
				(x2, y2) = (point2[0], point2[1])
				if x1 == x2 or y1 == y2:
					continue
				if (x1, y2) in pointSet and (x2, y1) in pointSet:
					area = abs(x2 - x1) * abs(y2 - y1)
					minArea = min(minArea, area)
		if minArea == sys.maxsize:
			return 0
		return minArea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:

		def hashing(i, j, p=40001):
			return i * p + j
		board = set()
		for (x, y) in points:
			board.add(hashing(x, y))
		ans = float('inf')
		print(board)
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				(tlx, tly) = points[i]
				(brx, bry) = points[j]
				if tlx == brx or tly == bry:
					continue
				if hashing(tlx, bry) in board and hashing(brx, tly) in board:
					ans = min(ans, abs((brx - tlx) * (bry - tly)))
		if ans < float('inf'):
			return ans
		else:
			return 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		y2x = collections.defaultdict(list)
		for (x, y) in points:
			y2x[y].append(x)
		res = float('inf')
		ys = list(y2x.keys())
		for y1 in ys:
			for y2 in ys:
				if y1 != y2:
					x1List = y2x[y1]
					x2Set = y2x[y2]
					canList = []
					for x1 in x1List:
						if x1 in x2Set:
							canList.append(x1)
					for m in canList:
						for n in canList:
							if m != n:
								res = min(res, abs(m - n) * abs(y1 - y2))
		if res == float('inf'):
			return 0
		return res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		if n < 4:
			return 0
		ptSet = set([(x, y) for (x, y) in points])
		area = math.inf
		for i in range(n):
			for j in range(i):
				if points[i][0] != points[j][0] and points[i][1] != points[j][1]:
					if (points[i][0], points[j][1]) in ptSet and (points[j][0], points[i][1]) in ptSet:
						area = min(area, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]))
		return area if area < math.inf else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		n = len(points)
		pmap = {(i, j) for (i, j) in points}
		area = float('inf')
		for i in range(n):
			for j in range(i + 1, n):
				x1 = points[i][0]
				y1 = points[i][1]
				x2 = points[j][0]
				y2 = points[j][1]
				if x1 != x2 and y2 != y1 and (x1 != y2) and (x2 != y1):
					if (x1, y2) in pmap and (x2, y1) in pmap:
						area = min(area, abs(x1 - x2) * abs(y2 - y1))
		return 0 if area == float('inf') else area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		area = float('inf')
		x_order = collections.defaultdict(list)
		y_order = collections.defaultdict(list)
		for p in points:
			x_order[p[0]].append(p[1])
			y_order[p[1]].append(p[0])
		xs = sorted(list(x_order.items()), key=lambda x: x[0])
		for col in xs:
			if len(col[1]) < 2:
				continue
			for i in range(len(col[1]) - 1):
				j = i + 1
				while j < len(col[1]):
					common_x = list(set(y_order[col[1][i]]) & set(y_order[col[1][j]]))
					common_x.remove(col[0])
					if common_x:
						for x in common_x:
							a = abs(col[0] - x) * abs(col[1][i] - col[1][j])
							area = min(area, a)
					j += 1
		return area if area < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		if n < 4:
			return 0
		s = set([tuple(i) for i in points])
		minarea = float('inf')
		for i in range(n - 1):
			for j in range(i + 1, n):
				if points[i][0] != points[j][0] and points[i][1] != points[j][1]:
					if (points[j][0], points[i][1]) in s and (points[i][0], points[j][1]) in s:
						minarea = min(minarea, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]))
		if minarea == float('inf'):
			return 0
		return minarea


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if len(points) < 4:
			return 0
		area = float('inf')
		corners = set([tuple(x) for x in points])
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				if points[i][0] != points[j][0] and points[i][1] != points[j][1]:
					if (points[i][0], points[j][1]) in corners and (points[j][0], points[i][1]) in corners:
						(l, w) = (abs(points[i][0] - points[j][0]), abs(points[i][1] - points[j][1]))
						area = min(area, l * w)
		return 0 if area == float('inf') else area


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pointsSet = set([(x, y) for (x, y) in points])
		minv = float('inf')
		for i in range(len(points)):
			for j in range(i + 1, len(points)):
				if points[i][0] != points[j][0] and points[i][1] != points[j][1] and ((points[i][0], points[j][1]) in pointsSet) and ((points[j][0], points[i][1]) in pointsSet):
					minv = min(minv, abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]))
					if minv == 1:
						print((points[i], points[j]))
		return minv if minv != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_set = {tuple(p) for p in points}
		res = float('inf')
		for p1 in points:
			for p2 in points:
				if p1[0] != p2[0] and p1[1] != p2[1]:
					area = abs(p1[0] - p2[0]) * abs(p1[1] - p2[1])
					if area < res:
						if (p1[0], p2[1]) in points_set and (p2[0], p1[1]) in points_set:
							res = area
		return 0 if res == float('inf') else res


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		pts = set()
		for p in points:
			pts.add((p[0], p[1]))
		ans = float('inf')
		flag = False
		P = len(points)
		for i in range(P):
			for j in range(i + 1, P):
				if points[i][0] == points[j][0] or points[i][1] == points[j][1]:
					continue
				else:
					dx1 = points[i][0]
					dy1 = points[j][1]
					dx2 = points[j][0]
					dy2 = points[i][1]
					if (dx1, dy1) in pts and (dx2, dy2) in pts:
						area = abs(dy1 - dy2) * abs(dx1 - dx2)
						ans = min(area, ans)
						flag = True
		return ans if flag else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points):
		points.sort()
		columns = defaultdict(list)
		for (r, c) in points:
			columns[r].append(c)
		(ans, lastc) = (float('inf'), dict())
		for (r, cols) in columns.items():
			for (i, c1) in enumerate(cols):
				for c2 in cols[i + 1:]:
					if (c1, c2) in lastc:
						area = (r - lastc[c1, c2]) * (c2 - c1)
						if area < ans:
							ans = area
					lastc[c1, c2] = r
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		len_x = {x for (x, y) in points}
		len_y = {y for (x, y) in points}
		if len(len_x) == len(points) or len(len_y) == len(points):
			return 0
		memo = collections.defaultdict(list)
		if len_x > len_y:
			for (x, y) in points:
				memo[x].append(y)
		else:
			for (x, y) in points:
				memo[y].append(x)
		res = float('inf')
		memo2 = {}
		for i in sorted(memo):
			memo[i].sort()
			for j in range(len(memo[i])):
				for k in range(j + 1, len(memo[i])):
					if (memo[i][j], memo[i][k]) in memo2:
						res = min(res, (memo[i][k] - memo[i][j]) * abs(memo2[memo[i][j], memo[i][k]] - i))
					memo2[memo[i][j], memo[i][k]] = i
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points.sort()
		xs = collections.defaultdict(list)
		for (x, y) in points:
			xs[x].append(y)
		seen = {}
		result = math.inf
		for (x, ylist) in xs.items():
			for ys in itertools.combinations(ylist, 2):
				if ys in seen:
					result = min(result, (x - seen[ys]) * (ys[1] - ys[0]))
				seen[ys] = x
		return 0 if math.isinf(result) else result


class Solution(object):

	def minAreaRect(self, points):
		y_group = collections.defaultdict(list)
		for (x, y) in points:
			y_group[x].append(y)
		visited = {}
		area = inf
		for x in sorted(y_group):
			Y = y_group[x]
			Y.sort()
			for i in range(len(Y)):
				y1 = Y[i]
				for j in range(i):
					y2 = Y[j]
					if (y1, y2) in visited:
						area = min((x - visited[y1, y2]) * (y1 - y2), area)
					visited[y1, y2] = x
		return area if area < inf else 0


class Solution:

	def minAreaRectangularHull(self, points: List[List[int]]) -> int:
		area = 0
		if points:
			(minx, miny) = points[0]
			(maxx, maxy) = points[0]
			for (x, y) in points:
				minx = min(minx, x)
				miny = min(miny, y)
				maxx = max(maxx, x)
				maxy = max(maxy, y)
			area = (maxx - minx) * (maxy - miny)
		return area

	def minAreaRect(self, points):
		S = set(map(tuple, points))
		ans = float('inf')
		for (k, (xB, yB)) in enumerate(points):
			for j in range(k):
				(xA, yA) = points[j]
				if xA != xB and yA != yB and ((xA, yB) in S) and ((xB, yA) in S):
					ans = min(ans, abs((xB - xA) * (yB - yA)))
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		columns = collections.defaultdict(set)
		for (x, y) in points:
			columns[x].add(y)
		lastx = {}
		ans = float('inf')
		for x in sorted(columns):
			column = sorted(columns[x])
			for (j, y2) in enumerate(column):
				for i in range(j):
					y1 = column[i]
					if (y1, y2) in lastx:
						ans = min(ans, (x - lastx[y1, y2]) * (y2 - y1))
					lastx[y1, y2] = x
		return ans if ans < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		points_dict = collections.defaultdict(list)
		for (x, y) in points:
			points_dict[x].append(y)
		points_dict = dict(sorted(list(points_dict.items()), key=lambda x: x[0]))
		seen_ys = dict()
		result = float('inf')
		for x in list(points_dict.keys()):
			ys = sorted(points_dict[x])
			print((x, ys))
			for (i, y2) in enumerate(ys):
				for j in range(i):
					y1 = ys[j]
					if (y1, y2) in seen_ys:
						result = min(result, (y2 - y1) * (x - seen_ys[y1, y2]))
					seen_ys[y1, y2] = x
		return result if result < float('inf') else 0


from collections import defaultdict

class Solution(object):

	def minAreaRect(self, points):
		x_points = defaultdict(list)
		for (x, y) in points:
			x_points[x].append(y)
		min_area = float('inf')
		vert_lines = {}
		sort_by_x = sorted(x_points)
		for x in sort_by_x:
			y_list = x_points[x]
			y_list.sort()
			for i in range(len(y_list)):
				y2 = y_list[i]
				for j in range(i):
					y1 = y_list[j]
					if (y1, y2) in vert_lines:
						x2 = vert_lines[y1, y2]
						min_area = min(min_area, abs(x - x2) * abs(y1 - y2))
					vert_lines[y1, y2] = x
		return min_area if min_area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		collection = collections.defaultdict(list)
		for (x, y) in points:
			collection[x].append(y)
		result = float('inf')
		previousx = {}
		for x in sorted(collection):
			column = collection[x]
			column.sort()
			for (j, y2) in enumerate(column):
				for i in range(j):
					y1 = column[i]
					if (y1, y2) in previousx:
						result = min(result, (x - previousx[y1, y2]) * (y2 - y1))
					previousx[y1, y2] = x
		if result < float('inf'):
			return result
		return 0


class Solution:

	def minAreaRect(self, points):
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				if p1x != p2x and p1y != p2y and ((p1x, p2y) in pSet) and ((p2x, p1y) in pSet):
					ans = min(ans, abs((p1x - p2x) * (p1y - p2y)))
		return ans if ans < float('inf') else 0

class Solution:

	def minAreaRect(self, points):
		X = list(zip(*points))
		if len(set(X[0])) == 1 or len(set(X[1])) == 1:
			return 0
		(pSet, ans) = (set(map(tuple, points)), float('inf'))
		for (i, (p1x, p1y)) in enumerate(points):
			for (p2x, p2y) in points[i + 1:]:
				area = abs((p2x - p1x) * (p2y - p1y))
				if area > ans or area == 0:
					continue
				if (p1x, p2y) in pSet and (p2x, p1y) in pSet:
					ans = area
		return ans if ans < float('inf') else 0


from collections import defaultdict

class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		n = len(points)
		if n < 4:
			return 0
		d = defaultdict(set)
		for (x, y) in points:
			d[x].add(y)
		xs = sorted(d.keys())
		ans = float('inf')
		exist = False
		for i in range(len(xs) - 1):
			x1 = xs[i]
			ys1 = d[x1]
			for j in range(i + 1, len(xs)):
				x2 = xs[j]
				ys2 = d[x2]
				ys = sorted(ys1 & ys2)
				if len(ys) >= 2:
					exist = True
					minHeight = ys[1] - ys[0]
					for j in range(2, len(ys)):
						minHeight = min(minHeight, ys[j] - ys[j - 1])
					ans = min(ans, minHeight * (x2 - x1))
		return 0 if not exist else ans


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		columns = collections.defaultdict(list)
		res = float('inf')
		for (x, y) in points:
			columns[x].append(y)
		y_pairs = dict()
		for x in sorted(columns):
			ys = sorted(columns[x])
			for i in range(len(ys) - 1):
				for j in range(i + 1, len(ys)):
					if (ys[i], ys[j]) in y_pairs:
						res = min(res, (x - y_pairs[ys[i], ys[j]]) * (ys[j] - ys[i]))
					y_pairs[ys[i], ys[j]] = x
		return res if res != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		res = float('inf')
		(xs, ys) = (collections.defaultdict(set), collections.defaultdict(set))
		for (x1, y1) in points:
			for x2 in xs[y1]:
				for y2 in ys[x1]:
					if x2 in xs[y2]:
						res = min(res, abs(x2 - x1) * abs(y2 - y1))
			xs[y1].add(x1)
			ys[x1].add(y1)
		return res if res < float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		result = float('inf')
		columns = collections.defaultdict(lambda : [])
		for (x, y) in points:
			columns[x].append(y)
		print('columns is: ' + str(columns))
		lastSeen = {}
		for x in sorted(columns.keys()):
			column = sorted(columns[x])
			for i in range(len(column)):
				y1 = column[i]
				for j in range(i + 1, len(column)):
					if y1 != column[j]:
						y2 = column[j]
						if (y1, y2) in lastSeen:
							prev_x = lastSeen[y1, y2]
							result = min(result, (y2 - y1) * (x - prev_x))
						lastSeen[y1, y2] = x
		return 0 if result == float('inf') else result


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		if not points:
			return 0
		x_map = {}
		points.sort(key=lambda x: x)
		area = float('inf')
		y_map = {}
		for point in points:
			if point[0] in x_map:
				x_map[point[0]].append(point[1])
				continue
			x_map[point[0]] = [point[1]]
		for x in x_map:
			x_map[x].sort()
			for j in range(0, len(x_map[x])):
				y2 = x_map[x][j]
				for k in range(0, j):
					y1 = x_map[x][k]
					if (y1, y2) in y_map:
						area = min(area, (y2 - y1) * (x - y_map[y1, y2]))
					y_map[y1, y2] = x
		return area if area != float('inf') else 0


class Solution:

	def minAreaRect(self, points: List[List[int]]) -> int:
		vsides = dict()
		for (x, y) in points:
			if x in vsides:
				vsides[x].append(y)
			else:
				vsides[x] = [y]
		slengths = dict()
		min_area = float('inf')
		xs = list(vsides.keys())
		xs.sort()
		for x in xs:
			vs = vsides[x]
			vs.sort()
			for i in range(len(vs) - 1):
				for j in range(i + 1, len(vs)):
					if (vs[i], vs[j]) in slengths:
						area = abs((x - slengths[vs[i], vs[j]]) * (vs[j] - vs[i]))
						min_area = min(min_area, area)
					slengths[vs[i], vs[j]] = x
		return min_area if min_area != float('inf') else 0