Let's first find the total length of grid line segments which lie strictly inside the given polygon and are horizontal. Assume that we cut the given polygon by horizontal grid lines. Therefore, the polygon will be cut into trapezoids and triangles with height ~1~. Bases of trapezoids and triangles are horizontal segments (we may think that a triangle is a trapezoid with one base length equal to ~0~). Now the area of a polygon can be expressed as the sum of trapezoid areas:

$$\displaystyle \text{Polygon_area} = \sum_i \text{trapezoid}_i \frac{\text{base}_1 +\text{base}_2}{2}$$

On the other hand, the area of the polygon can be calculated using only given vertex coordinates ~x_i~ and ~y_i~ in the given order as:

$$\displaystyle \text{Polygon_area} = \frac{\left|\sum_{i=1}^N x_i y_{i+1} - x_{i+1} y_i\right|}{2}$$

In this formula ~x_{N+1} = x_1~ and ~y_{N+1} = y_1~.

Every horizontal gridline segment appears in the sum at most twice (zero times if it is outside polygon, once if it is on the polygon's side and twice if it is strictly inside). These segments which appear two times in sum has total weight ~1~ ~(0.5 + 0.5)~. Segments that appear only once have total weight ~0.5~.

To calculate the total sum of segments that lie strictly inside the polygon, we need to subtract from the polygon area (calculated using formula ~2~) the total length of horizontal polygon perimeter segments divided by ~2~.

Total length of vertical gridline segments can be calculated in exactly the same way.

It is easy to see that the correct answer multiplied by ~2~ always is an integer so there is no need to do calculations in the floating point numbers.

Algorithm complexity is ~\mathcal O(N)~.

For the given constraints all calculations can be done using ~64~ bit integers.