P4671 [BalticOI 2011] Polygon (Day2)

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).

无

无

**Sample Explanation 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 Explanation 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$. **数据范围** 对于 $50\%$ 的数据，多边形所有的边均在网格线上。 对于所有数据，$3 \le N \le 10^5,-5 \times 10^8 \le x,y \le 5 \times 10^8$。