Rectangles in a Clipped Grid

Counting rectangles in an irregularly shaped grid

This is a medium-difficulty combinatorial counting problem that tests your ability to systematically enumerate geometric objects within a non-standard shape. Rather than a regular rectangular grid, you must work with a cross-shaped region and account for its irregular boundaries.

To solve problems like this, candidates typically identify all valid rectangle positions by considering which pairs of horizontal and vertical lines (or boundaries) can form the sides of a rectangle entirely contained within the shape. The key challenge is avoiding overcounting while ensuring no valid rectangles are missed. Many approaches benefit from breaking the shape into regions or leveraging symmetry to reduce case work.

• Systematic enumeration of geometric objects
• Boundary constraints and shape irregularity
• Exploiting symmetry to simplify counting
• Verification of edge cases and overlapping regions