Maximizing Dance Participation

The public square of LQ City is paved with marble tiles that form a perfect grid. The square itself is in the shape of a polygon whose vertices are grid intersections (i.e. points with integer coordinates). A tile is considered complete if none of its four corners lie on the polygon boundary. During the evening, each dancer picks one complete tile to dance on, and no two dancers may choose the same tile. Given the shape of the square by its vertices in order, compute the maximum number of dancers that can participate simultaneously.

A common approach is to iterate over all candidate grid cells (tiles) whose bottom‐left corners (i, j) range from min_x+1 to max_x-1 and min_y+1 to max_y-1, and for each cell, check if the four corners (i, j), (i+1, j), (i, j+1), and (i+1, j+1) are strictly inside the polygon. Points on the boundary are considered outside. One may use the ray-casting algorithm for point-in-polygon determination. For example, for a rectangle with vertices at (0,0), (4,0), (4,3), and (0,3), the number of complete tiles is \((4-2)\times(3-2)=2\).

All formulas, such as the one for a rectangle: \( \text{count}=(m-2)\times(n-2) \), must be written using \( \LaTeX \) format.

inputFormat

The input begins with an integer n (the number of vertices). The next n lines each contain two integers representing the x and y coordinates of the polygon's vertices in order. All coordinates are integers.

outputFormat

Output a single integer representing the maximum number of complete tiles on which dancers can perform.

sample

4
0 0
4 0
4 3
0 3

2