Baltic Olympiad in Informatics: 2011 Day 2, Problem 3

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 of its edges intersect or touch. All vertices of the polygon 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 (these line segments are highlighted in the drawings below).

Constraints

$3\le N\le {10}^5$

$|x|,|y|\le 5\times {10}^8$

Input Specification

The first line of input contains a single integer $N$, the number of vertices of the polygon. Each of the following $N$ lines contains two integers $x$ and $y$, the coordinates of one vertex. The vertices are given either in clockwise or counterclockwise order. All vertices are distinct, but more than two consecutive vertices may lie on a line.

Output Specification

The only line of output must contain a decimal number: the total length of grid line segments which lie strictly inside the given polygon.

Your answer will be accepted if it is within a relative error of ${10}^{-6}$ of the answer.

Sample Input 1

3
5 1
2 4
1 1

Sample Output 1

10.0

Explanation for Sample 1

The length of horizontal lines is $\frac{4}{3}+\frac{8}{3}=4$. The length of vertical lines is $3+2+1=6$. The total length is $4+6=10$.

Sample Input 2

5
0 0
-2 2
-2 -1
2 -2
2 0

Sample Output 2

12.5

Explanation for Sample 2

The length of horizontal lines is $1+2+4=7$. The length of vertical lines is $\frac{9}{4}+\frac{3}{2}+\frac{7}{4}=5.5$. The total length is $7+5.5=12.5$.