ZOJ Problem Set - 3364
Consider an infinite chessboard. Introduce a coordinate system on it in such a way that chessboard cells are unit squares with integer corner coordates. Let the cells be colored black and white like on the standard chessboard, let the cell with bottom left corner at (0,0) be colored black.
Somebody has drawn a closed polyline on the board. The vertices of the polyline are in the corners of the cells and its sides are parallel to the coordinate axes. It's interesting, what is the number of black and white cells inside the polyline. Find that out.
The first line of the input file contains n --- the number of vertices of the polyline (1 ≤ n ≤ 50000). The following n lines contain the coordinates of the vertices in counter-clockwise order. Coordinates are integer and do not exceed 109 by their absolute values. Polyline has no self-intersections and no self-touchings.
There are multiple cases. Process to the end of file.
Output two numbers: b and w --- the number of black and white cells inside the polyline repectively.
12 1 0 2 0 2 1 3 1 3 2 2 2 2 3 1 3 1 2 0 2 0 1 1 1
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11