0872MediumArrayHash TableMathGeometry

Smallest Slanted Frame

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def smallest_slanted_frame(points: list[list[int]]) -> float:

Java

public double smallestSlantedFrame(List<List<Integer>> points)

The intended approach

Time O(n^2) pairs grouped, then work proportional to the pairs sharing each key, which is O(n^4) in the worst case for the declared pin count of at most fifty.Space O(n^2) for the groups of pairs.

A rectangle is fixed by its two diagonals: they must share a midpoint and be the same length. So group the pin pairs by that pair of facts, using the midpoint doubled and the squared length so everything stays in whole numbers and nothing drifts. Any two pairs in the same group are the two diagonals of a rectangle, and its side lengths come from the distances between an endpoint of one diagonal and the two endpoints of the other. Take the smallest area found over every such combination.

Pythonentry point: smallest_slanted_frame

def smallest_slanted_frame(points):
    n = len(points)
    groups = {}
    for a in range(n):
        for b in range(a + 1, n):
            ax, ay = points[a]
            bx, by = points[b]
            # doubled midpoint and squared length keep the key exact
            key = (ax + bx, ay + by, (ax - bx) ** 2 + (ay - by) ** 2)
            groups.setdefault(key, []).append((a, b))
    best = None
    for pairs in groups.values():
        if len(pairs) < 2:
            continue
        for i in range(len(pairs)):
            for j in range(i + 1, len(pairs)):
                p, q = pairs[i]
                r, _t = pairs[j]
                px, py = points[p]
                rx, ry = points[r]
                qx, qy = points[q]
                side1 = ((px - rx) ** 2 + (py - ry) ** 2) ** 0.5
                side2 = ((qx - rx) ** 2 + (qy - ry) ** 2) ** 0.5
                area = side1 * side2
                if best is None or area < best:
                    best = area
    return 0.0 if best is None else float(best)

The obvious version

Try every four pins and every way of ordering them round a shape, checking directly that the four corners give equal opposite sides and a right angle at each corner, then take the area. Quartic in the pin count and makes no argument about diagonals.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_smallest_slanted_frame(points):
    import itertools
    best = None
    n = len(points)
    for quad in itertools.combinations(range(n), 4):
        for order in itertools.permutations(quad):
            a, b, c, d = (points[i] for i in order)
            # walk the four corners and require each turn to be a right angle
            def sub(p, q):
                return (p[0] - q[0], p[1] - q[1])

            def dot(p, q):
                return p[0] * q[0] + p[1] * q[1]

            e1 = sub(b, a)
            e2 = sub(c, b)
            e3 = sub(d, c)
            e4 = sub(a, d)
            if dot(e1, e2) != 0 or dot(e2, e3) != 0 or dot(e3, e4) != 0:
                continue
            if e1 == (0, 0) or e2 == (0, 0):
                continue
            side1 = (e1[0] ** 2 + e1[1] ** 2) ** 0.5
            side2 = (e2[0] ** 2 + e2[1] ** 2) ** 0.5
            area = side1 * side2
            if best is None or area < best:
                best = area
    return 0.0 if best is None else float(best)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in