Polygon
A polygon is defined by n vertices and is situated on an infinite rectangular grid. Each vertex of the polygon has integer coordinates, and the polygon's sides do not intersect. Your task is to determine the total length of the grid line segments that lie strictly within the polygon (refer to the figures below for clarification).
Input
The first line contains the integer n (3 ≤ n ≤ 100,000), representing the number of vertices. Each of the following n lines contains two integers, which are the coordinates of the polygon's vertices (-5∙10^8 ≤ x, y ≤ 5∙10^8). The coordinates are provided in either a clockwise or counterclockwise sequence.
Output
Output a single number with a precision of 3 decimal places, representing the total length of the grid line segments that lie strictly within the polygon.
Explanation of the first test
Total length of horizontal lines: 4/3 + 8/3 = 4
Total length of vertical lines: 3 + 2 + 1 = 6
Therefore, the total length is 4 + 6 = 10
Explanation of the second test
Total length of horizontal lines: 1 + 2 + 4 = 7
Total length of vertical lines: 9/4 + 3/2 + 7/4 = 5.5
Therefore, the total length is 7 + 5.5 = 12.5