Algorithms / Points And Rectangles
Least You Need to Know: Points, Rectangles, Manhattan Distance, and Coordinate Checks
Coordinate interview problems reward small geometric invariants: compare min and max coordinates, use Manhattan distance when movement is axis-aligned, and rely on cross-product or area-style reasoning instead of fragile slope arithmetic when possible.
The least you need to know
- An axis-aligned rectangle with corners `(x1, y1)` and `(x2, y2)` has area `(x2 - x1)(y2 - y1)` when `x2 > x1` and `y2 > y1`.
- The Manhattan distance between two points is `|x1 - x2| + |y1 - y2|`.
- Bounding boxes come from independent min/max operations on x- and y-coordinates.
- Collinearity is often safer to test with a zero-area or cross-product condition than with floating-point slopes.
- Coordinate problems often become easier once you separate x-axis facts from y-axis facts.
Key notation
|x1-x2| + |y1-y2|
Manhattan distance
(x2-x1)(y2-y1)
axis-aligned rectangle area
cross((b-a),(c-a))
orientation/collinearity test
Tiny worked example
- For points `(1, 2)` and `(4, 6)`, the Manhattan distance is `|1-4| + |2-6| = 7`.
- If you instead need the area of the axis-aligned rectangle with opposite corners `(1, 2)` and `(4, 6)`, compute width `3` times height `4` to get `12`.
Common mistakes
- Using Euclidean-distance intuition in an axis-aligned-move problem leads to the wrong metric.
- Bounding rectangles are coordinatewise min/max problems, not sorting-all-points problems.
- Slope comparisons can hide division-by-zero or precision issues that cross products avoid.
How to recognize this kind of problem
- The task asks about rectangles aligned to axes, nearest points under taxicab motion, or containment by coordinate ranges.
- The geometry separates naturally into independent x and y conditions.
- A shape or path is defined by horizontal and vertical moves rather than arbitrary angles.