题目描述
I have bought an island where I want to plant trees in rows and columns. The trees will be planted to form a rectangular grid, so each can be thought of as having integer coordinates by taking a suitable grid point as the origin.
A sample of my island
However, my island is not rectangular. 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.
I seek your help in calculating the number of trees that can be planted.
输入
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 in either the clockwise or counterclockwise direction. Each of these N lines contains two integers identifying the x- and y-coordinates of a vertex. You may assume that the absolute value of all coordinates will be no larger than 1,000,000.
A test case containing a zero for N in the first line terminates the input.
输出
For each test case, print a line containing the number of trees that can be planted inside the polygon.
样例输入
12
3 1
6 3
9 2
8 4
9 6
9 9
8 9
6 5
5 8
4 4
3 5
1 3
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
样例输出
21
25990001
参考代码
暂无
解析
暂无
