다각형의 넓이

오늘 요코(Yoko)의 수학 숙제는 xy 평면 위에 있는 다각형들의 넓이를 계산하는 것이었습니다. 꼭짓점은 모두 격자점 위에 놓여 있습니다(즉, 정수 좌표를 가집니다).

여러분이 할 일은 수학도 컴퓨터 프로그래밍도 잘하지 못하는 요코가 숙제를 끝내도록 돕는 것입니다. 다각형은 그 꼭짓점들의 좌표를 나열하여 주어집니다. 여러분의 프로그램은 다각형과 겹치는 단위 정사각형(그 꼭짓점 또한 격자점인 $1 \times 1$ 정사각형)의 개수를 세어 그 넓이를 근사해야 합니다. 정확히 말하면, 단위 정사각형이 "다각형과 겹친다"는 것은 그 둘의 교집합이 0이 아닌 넓이를 가질 때, 그리고 오직 그때뿐입니다. 아래 그림에서 점선으로 된 가로·세로 선은 격자선이고, 실선은 다각형의 변입니다. 색칠된 단위 정사각형이 다각형과 겹치는 것으로 간주됩니다. 이 다각형에 대해 여러분의 프로그램은 55를 출력해야 합니다(보다시피 색칠된 단위 정사각형의 개수는 55입니다).

그림 1: 다각형과, 그것에 겹치는 단위 정사각형들

입력은 다각형들을 차례로 기술하고, 마지막에는 $0$ 하나만 들어 있는 종료 줄이 옵니다.

각 다각형의 기술은 꼭짓점의 개수를 나타내는 정수 $m$ ($m \ge 3$) 하나가 들어 있는 줄로 시작합니다. 그 뒤로 $m$개의 줄이 이어지며, 각 줄에는 한 꼭짓점의 좌표인 두 정수 $x$와 $y$가 들어 있고 공백 하나로 구분됩니다. 이 $m$개 줄 중 $i$번째 줄은 $i$번째 꼭짓점의 좌표를 나타냅니다($i = 1, \cdots, m$). 각 $i = 1, \cdots, m-1$에 대해, $i$번째 꼭짓점과 $(i+1)$번째 꼭짓점은 변으로 연결됩니다. $m$번째 꼭짓점과 첫 번째 꼭짓점도 변으로 연결됩니다(즉, 곡선은 닫혀 있습니다). 변들은 꼭짓점에서만 만납니다. 어떤 세 변도 한 꼭짓점을 공유하지 않습니다(즉, 곡선은 단순합니다). 다각형의 개수는 $100$개를 넘지 않습니다. 각 다각형에서 꼭짓점의 개수 $m$은 $100$을 넘지 않습니다. 모든 좌표 $x$와 $y$는 $-2000 \le x \le 2000$과 $-2000 \le y \le 2000$을 만족합니다.

출력은 다각형의 개수만큼의 줄로 이루어져야 합니다. $k$번째 출력 줄에는 위에서 설명한 방식으로 근사한 $k$번째 다각형의 넓이인 정수를 출력해야 합니다. 공백을 포함하여 다른 어떤 문자도 출력해서는 안 됩니다.