Grid Line Segments Length

A simple polygon with \(N\) vertices is drawn on an infinite rectangular grid. For such a polygon, only neighboring edges touch at their common vertex; no other edges intersect or touch. All vertices lie on grid points (i.e., vertices have integer coordinates).

Your task is to find the total length of grid line segments which lie strictly inside the given polygon. A grid line segment is defined as a segment between two adjacent grid points (either horizontal or vertical). A segment is considered strictly inside if every point on that segment is inside the polygon (i.e. not on its boundary).

Note: To decide whether a grid segment is strictly inside, the solution tests several sample points along the segment.

The polygon is given by its vertices in order. The polygon does not self-intersect.

The formula for a straight line between two grid points is given in \(\LaTeX\) format. For example, a horizontal segment between \((x, y)\) and \((x+1, y)\) has length \(1\) and a vertical segment between \((x, y)\) and \((x, y+1)\) also has length \(1\).

inputFormat

The first line contains an integer \(N\) (\(3 \le N \le 10^5\)), the number of vertices of the polygon. The following \(N\) lines each contain two integers representing the coordinates of the vertices in order: \(x\) and \(y\). It is guaranteed that all vertices are grid points and the polygon is simple.

outputFormat

Output a single integer representing the total length of all grid line segments that lie strictly inside the polygon.

sample

4
0 0
0 2
2 2
2 0

0