TreesOnMyIsland

인기도:C(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

About TreesOnMyIsland

섬을 하나 구입했는데, 그 섬에 행과 열을 맞춰서 나무를 심으려고 한다. 나무들이 직사각 격자를 이루도록 심을 계획이므로, 적당한 격자점을 원점으로 잡으면 각 나무가 정수 좌표를 가지도록 할 수 있다. 다음 그림은 섬의 모양이다. [1] 그림에서 보다시피 섬은 직사각형 모양이 아니다. 그래서 섬 안쪽으로, 모든 꼭지점이 격자점 위에 있는 간단한 다각형을 그려서 그 다각형 안에 있는 격자점에 나무를 심기로 했다. 심을 수 있는 나무의 개수를 구해보자.

Input

입력 파일에 여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스는 다각형을 이루는 꼭지점의 개수를 나타내는 정수 N(3≤N≤1,000)으로 시작한다. 그 밑으로는 N 줄에 걸쳐서 다각형의 꼭지점 위치가 시계 방향 또는 반시계방향으로 순서대로 입력된다. 꼭지점의 위치는 x 좌표와 y 좌표를 나타내는 두 정수로 입력된다. 모든 좌표의 절대 값은 1,000,000 을 넘지 않는다고 할 수 있다. N으로 0이 입력되면 입력이 종료된다.

Output

각 테스트 케이스에 대해 주어진 다각형 안에 심을 수 있는 나무의 개수를 한 줄에 하나씩 출력한다.

Sample Input

{{| 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 |}}

Sample Output

풀이

작성자	사용언어	개발시간	코드

쓰레드

문제분류 경시대회준비반