Problem D
Trees on My Island
Input: standard input
Output: standard output
I have bought an island where I want to plant trees in rows and columns. So, the trees will form a rectangular grid and each of them can be thought of having integer coordinates by taking a suitable grid point as the origin.
But, the problem is that the island itself is not rectangular. So, I have identified a simple polygonal area inside the island with vertices on the grid points and have decided to plant trees on grid points lying strictly inside the polygon.
Now, I seek your help for calculating the number of trees that can be planted on my island.
Input
The input file may contain multiple test cases. Each test case begins with a line containing an integer N (3 <= N <= 1,000) identifying the number of vertices of the polygon. The next N lines contain the vertices of the polygon either in clockwise or in anti-clockwise direction. Each of these N lines contains two integers identifying the x and y-coordinates of a vertex. You may assume that none of the coordinates will be larger than 1,000,000 in absolute values.
A test case containing a zero for N in the first line terminates the input.
Output
For each test case in the input
print a line containing the number of trees that can be planted inside the
polygon.
Sample Input
12Sample Output
21