2320. The Narrowest Direction of a Convex Polygon

A strictly convex polygon is given by its n vertices in anticlockwise order, with no three vertices collinear. Print the SQUARE of its minimum width, as a fraction in lowest terms.

The width of a convex shape along a direction is the distance between the two parallel supporting lines perpendicular to it, and the minimum width is the narrowest such gap over all directions. It is the answer to "what is the narrowest slot this shape can pass through". The width itself is usually irrational, while its square is always rational, so the square is what the problem asks for.

the square (0,0) (4,0) (4,4) (0,4) -> 16 1 width 4 the strip (0,0) (6,0) (6,1) (0,1) -> 1 1 width 1 the triangle (0,0) (4,0) (0,3) -> 144 25 width 12/5

The third line is the one to check by hand. The narrowest direction of a 3-4-5 right triangle is perpendicular to the hypotenuse, and the altitude to the hypotenuse is 12/5, whose square is 144/25.

## What most people try first

Sampling directions. Try a few hundred angles, take the smallest width, and accept a near answer. That needs trigonometry, it is approximate, and it can miss the true minimum entirely when the polygon has a long thin feature. The second instinct is the diameter, which is the LARGEST width and comes from #2307, and is a different quantity: a long thin sliver has a large diameter and a tiny minimum width.

## The minimum width is realised flush against an edge

Here is the fact that turns a continuous search into a finite one. For the minimum-width direction, one of the two supporting lines contains an entire EDGE of the polygon. So it is enough to consider, for each edge, the distance from that edge's line to the farthest vertex:

for each edge (h[i], h[i+1]): far = max over vertices v of cross(h[i], h[i+1], v) width_i^2 = far^2 / |h[i+1] - h[i]|^2 answer = min over i of width_i^2

far is twice the area of the largest triangle on that edge, which equals the edge length times the height, so dividing by the edge length gives the height and squaring first keeps everything integral. All the vertices have the same cross-product sign because the polygon is anticlockwise, so the maximum of the signed cross product is also the maximum of its absolute value and no absolute value is needed.

## Why the minimum touches an edge

Think of the width as a function of the direction angle. Between two consecutive events, where an event is a supporting line becoming flush with an edge, both supporting lines touch single vertices, and the width is then a sinusoid in the angle, so it has no interior minimum on the interval unless the interval contains a stationary point. A stationary point of that sinusoid is where the two supporting lines are perpendicular to the segment joining the two touched vertices, and that configuration is a local MAXIMUM of the width, not a minimum, because moving away from it in either direction shortens the gap. So the minimum can only occur at an event, which is exactly a supporting line flush with an edge. This is also why the diameter, which is the maximum, is found by looking at vertex PAIRS, while the minimum width is found by looking at edges.

## Comparing the candidates, and why the coordinates are small

Each candidate is a fraction far^2 / len^2. Reduce it, then compare two candidates by cross multiplication rather than by evaluating them:

n1 / r1 < n2 / r2 is exactly n1 * r2 < n2 * r1

both denominators being squared lengths, hence positive. That is two doublings of width: one to square the cross product, one to cross multiply. So coordinates here satisfy |x|, |y| <= 100. At that bound a cross product reaches 8 * 10^4, its square 6.4 * 10^9, and the cross-multiplied product about 5.1 * 10^14, which overflows a signed 32-bit integer, whose limit is 2147483647, and which is below 2^53 = 9007199254740992, so a 64-bit integer is required and a JavaScript Number is exact. One declared test is a nine-vertex polygon near that bound whose two narrowest edges are close enough that a 32 bit build picks the wrong one and prints 38025 1 instead of 586124100 17197.

## Cost

The straightforward version is O(n^2): for each edge, scan every vertex. With n <= 1000 that is a million cross products. Rotating calipers brings it to O(n), because the farthest vertex from an edge advances monotonically as the edge rotates, exactly as in #2307.

Constraints - `3 <= n <= 1000` - `-100 <= x, y <= 100` - the polygon is strictly convex, given anticlockwise, with no three vertices collinear and no repeated vertex - the fraction must be in lowest terms with a positive denominator - a cross-multiplied product reaches about `5.1 * 10^14`, which is why the coordinate bound here is only `100`