Total Length of Grid Segments in a Polygon

A simple polygon with N vertices is drawn on an infinite square grid. Every vertex has integer coordinates. A polygon is simple if adjacent sides share exactly one endpoint and non-adjacent sides do not intersect or touch.

Find the total length of all portions of vertical and horizontal grid lines that lie inside the polygon. Portions that lie only on the boundary of the polygon are not counted as interior length.

The first line contains the number of vertices N. Each of the next N lines contains two integers x and y, the coordinates of one vertex.

The vertices are given in either clockwise or counterclockwise order, and all vertices are distinct.

Print the total length of grid-line portions contained inside the polygon.

An absolute or relative error of at most 10^-6 is accepted.

• 3 <= N <= 100000
• -500000000 <= x, y <= 500000000