You are given a set of points in the 2D plane, represented as an array points where points[i] = [x_i, y_i]. Your task is to find the minimum area of any rectangle that can be formed by these points, where the rectangle does not have to be axis-aligned. That is, the sides of the rectangle may be at any angle, not necessarily parallel to the axes.
Each rectangle must have its four vertices among the given points. If no rectangle can be formed, return 0.
The problem asks for rectangles that can be at any orientation, not just axis-aligned. A brute-force approach would be to check every quadruple of points to see if they form a rectangle, but that's computationally expensive.
For rectangles, two key geometric properties help:
To optimize, we can use a hash map to group all point pairs by their midpoint and length, and only check those pairs for rectangle formation.
Let's break down the solution step by step:
(midpoint, distance) to the list of point pairs.0.We use a hash map for efficient grouping, and the cross product for area calculation, which works for rectangles at any angle.
Suppose points = [[1,2],[2,1],[1,0],[0,1]].
Brute-force approach:
The optimized approach is feasible for n ≤ 50.
The key insight is that rectangles can be detected by grouping point pairs with equal midpoints and distances. This reduces the problem from checking all quadruples to clever pair grouping and vector math. Using the cross product allows accurate area calculation for rectangles at any orientation, and the hash map enables efficient grouping. This approach is both elegant and efficient for the problem constraints.
from collections import defaultdict
from itertools import combinations
import math
class Solution:
def minAreaFreeRect(self, points):
point_pairs = defaultdict(list)
n = len(points)
# Store all pairs by (midpoint, length squared)
for i in range(n):
for j in range(i+1, n):
x1, y1 = points[i]
x2, y2 = points[j]
mx = (x1 + x2) / 2
my = (y1 + y2) / 2
d = (x1 - x2) ** 2 + (y1 - y2) ** 2
point_pairs[(mx, my, d)].append((i, j))
min_area = float('inf')
for pairs in point_pairs.values():
if len(pairs) < 2:
continue
for (i1, j1), (i2, j2) in combinations(pairs, 2):
p1 = points[i1]
p2 = points[j1]
p3 = points[i2]
# Use p1 as reference, vectors p1p3 and p1p2
v1 = (p3[0] - p1[0], p3[1] - p1[1])
v2 = (p2[0] - p1[0], p2[1] - p1[1])
area = abs(v1[0]*v2[1] - v1[1]*v2[0])
if area:
min_area = min(min_area, area)
return 0 if min_area == float('inf') else min_area
#include <vector>
#include <unordered_map>
#include <tuple>
#include <cmath>
#include <limits>
#include <algorithm>
using namespace std;
class Solution {
public:
double minAreaFreeRect(vector<vector<int>>& points) {
unordered_map<string, vector<pair<int, int>>> m;
int n = points.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
double mx = (points[i][0] + points[j][0]) / 2.0;
double my = (points[i][1] + points[j][1]) / 2.0;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int d = dx * dx + dy * dy;
char buf[100];
sprintf(buf, "%.5f,%.5f,%d", mx, my, d);
m[buf].emplace_back(i, j);
}
}
double min_area = numeric_limits<double>::max();
for (auto& kv : m) {
auto& pairs = kv.second;
if (pairs.size() < 2) continue;
for (int i = 0; i < pairs.size(); ++i) {
for (int j = i + 1; j < pairs.size(); ++j) {
auto [a, b] = pairs[i];
auto [c, d_] = pairs[j];
auto& p1 = points[a];
auto& p2 = points[b];
auto& p3 = points[c];
// vectors: p1p3 and p1p2
double v1x = p3[0] - p1[0];
double v1y = p3[1] - p1[1];
double v2x = p2[0] - p1[0];
double v2y = p2[1] - p1[1];
double area = fabs(v1x * v2y - v1y * v2x);
if (area > 0) {
min_area = min(min_area, area);
}
}
}
}
return min_area == numeric_limits<double>::max() ? 0 : min_area;
}
};
import java.util.*;
class Solution {
public double minAreaFreeRect(int[][] points) {
Map<String, List<int[]>> map = new HashMap<>();
int n = points.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
double mx = (points[i][0] + points[j][0]) / 2.0;
double my = (points[i][1] + points[j][1]) / 2.0;
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int d = dx * dx + dy * dy;
String key = String.format("%.5f,%.5f,%d", mx, my, d);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{i, j});
}
}
double minArea = Double.MAX_VALUE;
for (List<int[]> pairs : map.values()) {
if (pairs.size() < 2) continue;
for (int i = 0; i < pairs.size(); ++i) {
for (int j = i + 1; j < pairs.size(); ++j) {
int[] a = pairs.get(i), b = pairs.get(j);
int[] p1 = points[a[0]], p2 = points[a[1]], p3 = points[b[0]];
double v1x = p3[0] - p1[0], v1y = p3[1] - p1[1];
double v2x = p2[0] - p1[0], v2y = p2[1] - p1[1];
double area = Math.abs(v1x * v2y - v1y * v2x);
if (area > 0) minArea = Math.min(minArea, area);
}
}
}
return minArea == Double.MAX_VALUE ? 0 : minArea;
}
}
var minAreaFreeRect = function(points) {
let map = new Map();
let n = points.length;
for (let i = 0; i < n; ++i) {
for (let j = i+1; j < n; ++j) {
let mx = (points[i][0] + points[j][0]) / 2;
let my = (points[i][1] + points[j][1]) / 2;
let dx = points[i][0] - points[j][0];
let dy = points[i][1] - points[j][1];
let d = dx * dx + dy * dy;
let key = mx.toFixed(5) + ',' + my.toFixed(5) + ',' + d;
if (!map.has(key)) map.set(key, []);
map.get(key).push([i, j]);
}
}
let minArea = Infinity;
for (let pairs of map.values()) {
if (pairs.length < 2) continue;
for (let i = 0; i < pairs.length; ++i) {
for (let j = i+1; j < pairs.length; ++j) {
let [i1, j1] = pairs[i], [i2, j2] = pairs[j];
let p1 = points[i1], p2 = points[j1], p3 = points[i2];
let v1x = p3[0] - p1[0], v1y = p3[1] - p1[1];
let v2x = p2[0] - p1[0], v2y = p2[1] - p1[1];
let area = Math.abs(v1x * v2y - v1y * v2x);
if (area > 0) minArea = Math.min(minArea, area);
}
}
}
return minArea === Infinity ? 0 : minArea;
};