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 is- land. 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 ei- ther 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 12 31 63 92 84 96 99 89 65 58 44 35 13 Figure: A sample of my island
2/2 12 1000 1000 2000 1000 4000 2000 6000 1000 8000 3000 8000 8000 7000 8000 5000 4000 4000 5000 3000 4000 3000 5000 1000 3000 0 Sample Output 21 25990001