Minimum Area Rectangle II
Problem
Given an array of points in the X-Y plane, find the minimum area of any rectangle formed using these points as vertices. The rectangle's sides need not be parallel to the axes — it may be rotated at any angle. Return 0 if no rectangle can be formed.
points = [[1,2], [2,1], [1,0], [0,1]]2.0def min_area_free_rect(points):
pts = {(x, y) for x, y in points}
best = float("inf")
n = len(points)
for i in range(n):
x1, y1 = points[i]
for j in range(n):
if j == i:
continue
x2, y2 = points[j]
for k in range(j + 1, n):
if k == i:
continue
x3, y3 = points[k]
# P2 and P3 share corner P1; P4 = P2 + P3 - P1
if (x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) != 0:
continue
x4, y4 = x2 + x3 - x1, y2 + y3 - y1
if (x4, y4) in pts:
d12 = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
d13 = ((x3 - x1) ** 2 + (y3 - y1) ** 2) ** 0.5
best = min(best, d12 * d13)
return 0.0 if best == float("inf") else bestfunction minAreaFreeRect(points) {
const pts = new Set(points.map(p => p[0] + "," + p[1]));
let best = Infinity;
const n = points.length;
for (let i = 0; i < n; i++) {
const [x1, y1] = points[i];
for (let j = 0; j < n; j++) {
if (j === i) continue;
const [x2, y2] = points[j];
for (let k = j + 1; k < n; k++) {
if (k === i) continue;
const [x3, y3] = points[k];
if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) !== 0) continue;
const x4 = x2 + x3 - x1, y4 = y2 + y3 - y1;
if (pts.has(x4 + "," + y4)) {
const d12 = Math.hypot(x2 - x1, y2 - y1);
const d13 = Math.hypot(x3 - x1, y3 - y1);
best = Math.min(best, d12 * d13);
}
}
}
}
return best === Infinity ? 0 : best;
}class Solution {
public double minAreaFreeRect(int[][] points) {
Set<Long> pts = new HashSet<>();
for (int[] p : points) pts.add(40001L * p[0] + p[1]);
double best = Double.MAX_VALUE;
int n = points.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
for (int k = j + 1; k < n; k++) {
if (k == i) continue;
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int x3 = points[k][0], y3 = points[k][1];
if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) != 0) continue;
long key = 40001L * (x2 + x3 - x1) + (y2 + y3 - y1);
if (pts.contains(key)) {
double d12 = Math.hypot(x2 - x1, y2 - y1);
double d13 = Math.hypot(x3 - x1, y3 - y1);
best = Math.min(best, d12 * d13);
}
}
}
}
return best == Double.MAX_VALUE ? 0 : best;
}
}double minAreaFreeRect(vector<vector<int>>& points) {
set<pair<int, int>> pts;
for (auto& p : points) pts.insert({p[0], p[1]});
double best = 1e18;
int n = points.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j == i) continue;
for (int k = j + 1; k < n; k++) {
if (k == i) continue;
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int x3 = points[k][0], y3 = points[k][1];
if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) != 0) continue;
if (pts.count({x2 + x3 - x1, y2 + y3 - y1})) {
double d12 = hypot(x2 - x1, y2 - y1);
double d13 = hypot(x3 - x1, y3 - y1);
best = min(best, d12 * d13);
}
}
}
}
return best == 1e18 ? 0 : best;
}Explanation
A rectangle is defined by one corner plus two right-angle sides. The idea is to pick a corner and two other points as its neighbors, check that the angle is square, and then verify the fourth corner actually exists.
First we drop every point into a hash set so we can ask "does this exact point exist?" instantly. Then three loops choose a corner P1 and two candidate neighbors P2 and P3.
For P1 to be a true right angle, the two side vectors must be perpendicular, which means their dot product is zero: (x2-x1)*(x3-x1) + (y2-y1)*(y3-y1) == 0. If it is not zero we skip.
When the angle is square, the missing fourth corner is forced to be P4 = P2 + P3 - P1. If P4 is in our set, we have a real rectangle, and its area is the product of the two side lengths d12 * d13. We keep the smallest such area in best.
Example: points (1,2),(2,1),(1,0),(0,1) form a tilted square. Taking (1,0) as the corner, the two sides have length √2 each, so the area is √2 * √2 = 2.0.