Description

The Citizens' Square in LQ City is a polygon, and the square is paved with marble floor tiles.

The tiles are laid in neat squares, just like graph paper.

Take a point where four tiles meet as the origin. Use the two edges of the tiles as the two positive directions. Let the side length of one tile be the unit length on both the $x$ and $y$ axes. Then, all points whose $x$ and $y$ coordinates are integers are intersections of four tiles (if they are inside the square).

Although the tiles are plain and boring, they provide excellent reference points for the citizens who dance in the square. Every evening, a large number of citizens come to dance.

Each dancer will choose one complete tile to dance on. No two people will choose the same tile. If a tile lies on the boundary of the square so that it is cut (missing a corner) or has an incomplete edge, then no one will choose that tile.

(See the picture for an example of the square's shape.)

Now you are given the shape of the square. Please help the mayor of LQ City calculate the maximum number of citizens who can dance in the square at the same time.

Input Format

The first line contains an integer $n$, indicating that the square is an $n$-gon (so it has $n$ vertices).

The next $n$ lines each contain two integers, giving the coordinates of the vertices of the $n$-gon in order (that is, every turning point of the boundary lies on a tile corner). The input guarantees that the square is a simple polygon.

Output Format

Output one integer, the maximum number of citizens who can dance in the square.

5
3 3
6 4
4 1
1 -1
0 4

7

Hint

Sample Explanation

As shown in the figure, there are $7$ complete floor tiles, so at most $7$ citizens can dance together.

Constraints

For $30\%$ of the testdata, $n \le 100$, and the absolute values of both coordinates are at most $100$.

For $50\%$ of the testdata, $n \le 1000$, and the absolute values of both coordinates are at most $1000$.

For $100\%$ of the testdata, $n \le 1000$, and the absolute values of both coordinates are at most $10^8$.

Time limit: 1 second, 256 MB. Lanqiao Cup 2016, the 7th edition.

Translated by ChatGPT 5