Total Length of Grid Segments in a Polygon

Time limit1sMemory limit128 MB

Summary

Given a simple polygon with integer vertices, compute the total length of grid line segments strictly inside the polygon.

Level: Hard8 of 10
Topics: Geometry, Sorting, Intervals
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

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

Constraints

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

Examples2

Example 1
Input
```
3
5 1
2 4
1 1
```
Expected output
```
10.0
```
Example 2
Input
```
5
0 0
-2 2
-2 -1
2 -2
2 0
```
Expected output
```
12.5
```