Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Area Rectangle II
Bookmark
Input
Forms rectangle
Multiple candidates
Square + extra
No rectangle
Custom
points
=
[[1,2],[2,1],[1,0],[0,1]]
groups · (midpoint, len²)
min area = ∞
a rectangle's two diagonals share a midpoint and a length
groups · (midpoint, len²)
min area = ∞
a rectangle's two diagonals share a midpoint and a length
groups · (midpoint, len²)
min area = ∞
midpoint (
1.5, 1.5
), length² =
2
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
min area = ∞
midpoint (
1, 1
), length² =
4
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×1
min area = ∞
pair
p0–p3
: a candidate diagonal
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×1
(0.5,1.5) ℓ²=2
×1
min area = ∞
pair
p1–p2
: a candidate diagonal
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×1
(0.5,1.5) ℓ²=2
×1
(1.5,0.5) ℓ²=2
×1
min area = ∞
group by that key →
1 pair
so far
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×2
(0.5,1.5) ℓ²=2
×1
(1.5,0.5) ℓ²=2
×1
min area = ∞
group by that key →
2 pairs
share it (rectangle!)
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×2
(0.5,1.5) ℓ²=2
×1
(1.5,0.5) ℓ²=2
×1
min area = ∞
midpoint (
0.5, 0.5
), length² =
2
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×2
(0.5,1.5) ℓ²=2
×1
(1.5,0.5) ℓ²=2
×1
(0.5,0.5) ℓ²=2
×1
min area = ∞
area = |1·-2 − -1·0| =
2
groups · (midpoint, len²)
(1.5,1.5) ℓ²=2
×1
(1,1) ℓ²=4
×2
(0.5,1.5) ℓ²=2
×1
(1.5,0.5) ℓ²=2
×1
(0.5,0.5) ℓ²=2
×1
min area = 2
minimum area rectangle =
2
algo
master
.
io
Step:
Find the minimum-area rectangle of any orientation
0 / 22
Input
Forms rectangle
Multiple candidates
Square + extra
No rectangle
Custom
points
=
[[1,2],[2,1],[1,0],[0,1]]
0 / 22
algo
master
.
io
Step:
Find the minimum-area rectangle of any orientation
