编程介的小学生
2017-04-20 10:30
采纳率: 19.4%
浏览 786
已采纳

Black and White

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.

Input

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

Output two numbers: b and w --- the number of black and white cells inside the polyline repectively.

Sample Input

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
Sample Output

1 4

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题