Hidden Grid Points in a Plot
HardMath & Geometry
Problem
A land plot is a simple polygon (its edges do not cross) whose corners are integer points, given in order around the boundary in vertices, either clockwise or counter-clockwise.
Trees can be planted only at integer grid points strictly inside the plot, not on its boundary. Return how many such points there are.
Example 1
- Input:
- vertices = [[0, 0], [4, 0], [4, 4], [0, 4]]
- Output:
- 9
The 3 × 3 block of points with x, y in 1..3.
Example 2
- Input:
- vertices = [[0, 0], [5, 0], [0, 5]]
- Output:
- 6
Points with x, y ≥ 1 and x + y ≤ 4.
Example 3
- Input:
- vertices = [[0, 0], [1, 0], [0, 1]]
- Output:
- 0
Constraints
- 3 ≤ vertices.length ≤ 10^4
- -10^4 ≤ x, y ≤ 10^4
- The polygon is simple and has positive area
Hint
Show the first hint
Scanning the bounding box can mean 4 · 10^8 point-in-polygon tests. Is there a formula linking area and grid points?
Walkthrough
How to approach it
01Clarify before coding
- Is the polygon simple? Yes; Pick's theorem needs that.
- Clockwise or counter-clockwise? Either: take the absolute value of the signed area.
- Can consecutive vertices be collinear? Yes; the formulas still hold.
- Do sums fit? Each shoelace term is at most 2 · 10^8 and there are 10^4 of them, so totals stay below 2 · 10^12.
02Brute force
For every grid point in the bounding box, run a ray-casting point-in-polygon test and exclude boundary points.
Cost: O(W · H · n): up to 4 · 10^8 points times 10^4 edges.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.