Minimum Area Rectangle II
Real-world version: Smallest Slanted FrameThe statement here is our own: the same inputs, outputs and technique.
A set of pin positions is given as points, each [x, y], and all of them are distinct.
A frame is four of those pins forming a rectangle. The rectangle's sides need not run along the axes, so a slanted rectangle counts.
Return the smallest area any frame can have, or 0.0 when no four pins form a rectangle. An answer within 1e-5 of the true value is accepted.
Examples
Example 1
- Input
- points = [[2, 10], [6, 13], [12, 5], [8, 2]]
- Output
- 50.0
The four pins form a rectangle standing at a slant. Its two diagonals both run between the midpoint 7, 7.5 and are the same length, and its sides measure 5 and 10, so the area is 50.
Example 2
- Input
- points = [[0, 0], [1, 0], [2, 0], [3, 0]]
- Output
- 0.0
Every pin sits on one line, so no four of them form a rectangle.
Example 3
- Input
- points = [[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]]
- Output
- 1.0
The smallest rectangle takes two neighbouring columns of pins, giving sides of 1 and 1.
Constraints
- 1 <= points.length <= 50
- points[i].length == 2
- 0 <= points[i][0] <= 40000
- 0 <= points[i][1] <= 40000
- All the pin positions are distinct
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def smallest_slanted_frame(points: list[list[int]]) -> float:public double smallestSlantedFrame(List<List<Integer>> points)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's