A decorative railing follows the boundary of a simple polygon whose n vertices have integer coordinates, listed in order around the perimeter. Support posts must be placed at every integer grid point that lies on the railing (on an edge or at a vertex). Count how many such boundary grid points there are.
Line 1: an integer n, the number of vertices.
Next n lines: two integers x y, the vertices in boundary order.
A single integer: the number of integer grid points on the polygon boundary.
Example 1
Input
3 0 0 4 0 0 4
Expected
12
Explanation
The three edges contribute 4 + 4 + 4 = 12 boundary grid points (each vertex counted once), so the answer is 12.
Example 2
Input
4 0 0 3 0 3 3 0 3
Expected
12
Explanation
Each side of this 3 by 3 square carries 3 grid steps, giving 12 boundary grid points in total.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →