Water Testing

Time limit2sMemory limit512 MB

Summary

Given the corner points of a simple polygon in order, count the integer lattice points that lie strictly inside it.

Level: Medium6 of 10
Topics: Geometry, Math, Number theory, Implementation
Solved: No attempts yet

Problem

You just bought a large piece of agricultural land, and you learned that regulations require you to test the ground water at specific points on your property once a year. Fortunately the description of these points is simple. The whole country is mapped in a Cartesian coordinate system, where $(0, 0)$ is the location of the Greenwich Observatory. The corners of all land properties lie at integer coordinates in this system. A ground water test point must be erected on every point inside a property whose coordinates are integers.

Input

The input consists of:

one line with a single integer $n$ ( $3 \le n \le 100\,000$ ), the number of corner points of your property;
$n$ lines, each containing two integers $x$ and $y$ ( $-10^6 \le x, y \le 10^6$ ), the coordinates of each corner.

The corners are given in the order they appear on the border of your property, and the polygon described by the points does not intersect itself.

Output

Output the number of points with integer coordinates that lie strictly inside your property.

Examples1

Example 1
Input
```
4
0 0
0 10
10 10
10 0
```
Expected output
```
81
```