Through the gap
A flat part (a tabletop, a sheet of plywood, a cut-out contour) must be carried through a narrow opening, keeping it in the plane of the opening and not turning it while it passes. It can be turned any way beforehand. What is the narrowest opening that is enough for it? And a second question from the same craftsman: what is the smallest-area rectangular sheet this part can be cut from?
The contour of the part is given by points, the vertices of its boundary, possibly mixed with points inside, repeats and points on the sides. The part is everything inside the boundary, so the points are enough for the answer.
Input
The first line holds n (3 ≤ n ≤ 2 · 105). Then n lines: integer coordinates x y, |x|, |y| ≤ 106. Not all points lie on one line.
Output
Two numbers separated by a space: the width of the narrowest opening and the area of the smallest rectangle. The answer is accepted if the error of each number is at most 10−6, and for numbers above one at most 10−6 of the answer.
Examples
Example 1
3 0 0 4 0 0 3
2.400000000 12.000000
Example 2
6 0 0 3 3 0 6 -3 3 0 3 1 3
4.242640687 18.000000
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
An opening the part passes through is a strip between two parallel lines. We need the narrowest strip into which the part fits entirely. Only the convex hull of the points matters: a strip and a rectangle are convex, and if the points lie in them, so does the hull.
2Hint 2
There are infinitely many directions, but there is no need to try them all. The narrowest strip has one edge on a side of the hull, and so does the smallest rectangle. So there are as many candidates as there are sides of the hull.
3The idea
Rotating calipers. For each side of the hull three vertices are needed: the one farthest from the side’s line, which gives the width of the strip, and the two extreme ones along the side, which give the length of the rectangle. On moving to the next side, all three vertices move only forward along the hull, so all sides take O(h) steps.
4Walkthrough
The hull is Andrew’s algorithm, counter-clockwise, without points on the sides. For a side AB with vector e: the height of a vertex P is the cross product (B − A) × (P − A), the position along the side the dot product e · (P − A). The farthest vertex j moves while the next one is higher; the right extreme r while the next one is farther along e; the left l while the next one is farther in the opposite direction. Starting positions for the first side: r from vertex zero, j from r, l from j. The strip’s width is height / |e|, the area height · (length along e) / |e|². All comparisons while moving are in integers.
4+Solution
5Complexity
O(n log n) for the hull and O(h) for the calipers, where h is the number of its vertices. On a circle of two hundred thousand points the hull has 11,744 vertices (the rest, after rounding to integers, fell inside or onto the sides), and brute force, “a side against all vertices”, O(h²), no longer makes it in time.
6Common mistakes
- Brute force. This is
wrong.py: on a thousand random points the hull has 16 vertices and it makes it; on a circle it does not. - A rectangle along the axes. For the triangle of the first example it happens to be optimal, but for a square standing on a corner it is twice as large as needed.
- The diameter instead of the width. The farthest pair of points determines how long the opening must be if the part is carried lengthwise; the width is a minimum over directions, not a maximum.
- Points on the sides of the hull. If they are kept, the hull gets sides with zero turn; the calipers work with them, but the strict comparisons when moving the pointers must allow for this. It is simpler to drop them when building the hull.
Algorithms behind it
O(n) after the hull, O(n log n) with it
2 problems
GEO
Algorithm
Convex hull
The smallest convex polygon containing all the points, in O(n log n).
O(n log n)
2 problems