Orchard fence count
MediumOnline Assessment
Count the fence posts and the trees of an orchard from its fence plan.
A surveyor's plan describes an orchard fence as a closed loop of straight sections. The list corners gives the corners of the fence in walking order, as [x, y] pairs of whole-number grid coordinates; the last corner connects back to the first. The fence never crosses or touches itself.
The orchard is laid out on the grid: a post stands on every grid point (both coordinates whole numbers) that lies anywhere on the fence line, including the corners and every grid point in the middle of a straight section. A tree is planted on every grid point strictly inside the fence. Grid points outside the fence get nothing.
Corners may be listed clockwise or counter-clockwise, and a corner may sit in the middle of a straight run (the fence just continues straight through it).
Input: corners, a list of [x, y] pairs.
Output: a list [posts, trees] of two integers.
The grid can be huge (coordinates up to ten million), so walking the grid point by point will not finish in time.
Example 1
- Input:
- [[[0,0],[4,0],[4,4],[0,4]]]
- Output:
- [16,9]
- Explanation
- A square fence with side 4 has 4 points per side, and counting each corner once gives 16 posts. The interior points are those with x and y both from 1 to 3, so there are 3 x 3 = 9 trees.
Example 2
- Input:
- [[[0,0],[6,0],[0,4]]]
- Output:
- [12,7]
- Explanation
- The slanted side from
[6, 0]to[0, 4]passes through the grid point[3, 2], so it contributes gcd(6, 4) = 2 sections of posts. Adding the sections 6 + 2 + 4 gives 12 posts, not just the 3 corners. The interior holds 7 trees.
Example 3
- Input:
- [[[0,0],[0,3],[0,6],[2,6],[2,2],[6,2],[6,0]]]
- Output:
- [24,9]
- Explanation
- The corners go clockwise, and
[0, 3]sits in the middle of a straight run, which adds nothing special. The L-shaped fence has sections of 6, 2, 4, 4, 2 and 6 grid steps, so 24 posts, and 9 trees inside.
Constraints
3 <= corners.length <= 60- every corner is
[x, y]with-10,000,000 <= x, y <= 10,000,000 - the corners, in order, trace a simple closed polygon: edges never cross or touch except consecutive edges at their shared corner, and no two consecutive corners are equal
- three or more consecutive corners may lie on one straight line