Apple trees on the grid
An apple orchard is planted by the ruler: trees stand at all points of a square grid with a step of one unit, that is, at all points with integer coordinates. A plot is fenced off by a polygon with vertices at grid points. Trees the fence passes through will have to be replanted. How many trees grow strictly inside the plot, and how many stand on the fence?
Coordinates go up to a billion, so trying the grid points will not work: the largest plot has about 4·10¹⁸ of them. The third test is the Auezov district of Almaty from OpenStreetMap, converted to integer metres on the grid of this catalogue’s road map: how many points of the metre grid are inside the district.
Input
The first line holds the number of vertices n (3 ≤ n ≤ 100,000). Then n lines with the integer coordinates of the vertices x y (|x|, |y| ≤ 10⁹) in order of traversal, clockwise or anticlockwise, whichever. The fence does not cross or touch itself: neighbouring sides meet only at a shared vertex, and the others have no common points. Vertices do not repeat, but three consecutive vertices may lie on one line.
Output
Two integers separated by a space: how many grid points lie strictly inside the polygon and how many on its boundary, including the vertices.
Examples
Example 1
5 1 1 7 2 6 6 4 4 2 7
18 6
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 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
Start with the fence. How many grid points lie on the segment from (0, 0) to (6, 4)? And to (6, 5)? Find the general rule for a segment with ends at grid points.
2Hint 2
The points inside cannot be tried, but the area of a polygon with vertices at grid points is computed exactly, by the shoelace formula, in integers. Area and the number of points are related: on squared paper a shape with many points inside has a large area too.
3Hint 3
This is Pick’s theorem: for a polygon with vertices at grid points S = I + B/2 − 1, where I is the points inside and B the points on the boundary. Check it on a 1 × 1 square and on a right triangle with legs 3 and 3.
4The idea
A side from (x₁, y₁) to (x₂, y₂) has gcd(|x₂ − x₁|, |y₂ − y₁|) + 1 grid points, counting both ends. If for each side only the end is counted and the start left to the previous side, you get B = Σ gcd(|Δx|, |Δy|) without repeats. The doubled area 2S is the absolute value of the shoelace sum, an integer. From Pick’s theorem 2I = 2S − B + 2.
5Walkthrough
Points on a side. Let Δx = x₂ − x₁, Δy = y₂ − y₁ and g = gcd(|Δx|, |Δy|). The points (x₁ + kΔx/g, y₁ + kΔy/g) for k = 0, 1, …, g are grid points on the side, g + 1 of them. There are no others: a point of the side is (x₁ + tΔx, y₁ + tΔy) with 0 ≤ t ≤ 1, and if both its coordinates are integers, then tΔx and tΔy are integers. Then t·g is an integer too: by Bézout’s identity g = aΔx + bΔy for some integers a and b, and tg = a·tΔx + b·tΔy. So t = k/g. The greatest common divisor is computed by Euclid’s algorithm.
The area. 2S = |Σ (xiyi+1 − xi+1yi)|, indices taken cyclically. The absolute value is needed because the direction of traversal is arbitrary.
The answer. I = (2S − B + 2) / 2, integer division: by Pick’s theorem the numerator is always even. Why Pick’s theorem holds is worked through in the article on polygon area.
About overflow in Go. The doubled area of a plot within a square of side 2·10⁹ is at most 8·10¹⁸, below the int64 limit (about 9.2·10¹⁸). Intermediate shoelace sums may go over the limit, but signed integers in Go wrap around modulo 2⁶⁴ on overflow, and a final result that itself fits in int64 comes out correct. The fifth test is a square over the whole field: 3,999,999,996,000,000,001 points inside.
5+Solution
6Complexity
O(n log C), where C ≤ 2·10⁹ is the largest coordinate difference: per side one product and one Euclidean algorithm, which needs O(log C) steps.
7Common mistakes
- Only vertices on the fence. The most common simplification: B = n. But a long side passes through many grid points: the triangle of the second test has three vertices and nine points on its boundary. This is the wrong solution of the problem, caught already by the example.
- The area through
float. Numbers up to 8·10¹⁸ do not fit in the mantissa of adouble(exact up to 2⁵³ ≈ 9·10¹⁵), and the last digits of the answer drift. Compute the doubled area in integers and divide by two only at the very end. - A forgotten absolute value. A clockwise traversal gives a negative shoelace sum, and without the absolute value the number of points inside comes out negative.
- Your own “is the point inside” check for every grid point. Correct, but there can be 4·10¹⁸ points. Even in the district of the third test there are 23 million of them, each with a pass over 536 sides: more than ten billion operations.