About TreesOnMyIsland ¶
섬을 하나 구입했는데, 그 섬에 행과 열을 맞춰서 나무를 심으려고 한다. 나무들이 직사각 격자를 이루도록 심을 계획이므로, 적당한 격자점을 원점으로 잡으면 각 나무가 정수 좌표를 가지도록 할 수 있다. 다음 그림은 섬의 모양이다.
http://online-judge.uva.es/p/v100/p10088.jpg
그림에서 보다시피 섬은 직사각형 모양이 아니다. 그래서 섬 안쪽으로, 모든 꼭지점이 격자점 위에 있는 간단한 다각형을 그려서 그 다각형 안에 있는 격자점에 나무를 심기로 했다. 심을 수 있는 나무의 개수를 구해보자.
http://online-judge.uva.es/p/v100/p10088.jpg
그림에서 보다시피 섬은 직사각형 모양이 아니다. 그래서 섬 안쪽으로, 모든 꼭지점이 격자점 위에 있는 간단한 다각형을 그려서 그 다각형 안에 있는 격자점에 나무를 심기로 했다. 심을 수 있는 나무의 개수를 구해보자.
Input ¶
입력 파일에 여러 테스트 케이스가 입력될 수 있다. 각 테스트 케이스는 다각형을 이루는 꼭지점의 개수를 나타내는 정수 N(3≤N≤1,000)으로 시작한다. 그 밑으로는 N 줄에 걸쳐서 다각형의 꼭지점 위치가 시계 방향 또는 반시계방향으로 순서대로 입력된다. 꼭지점의 위치는 x 좌표와 y 좌표를 나타내는 두 정수로 입력된다. 모든 좌표의 절대 값은 1,000,000 을 넘지 않는다고 할 수 있다.
N으로 0이 입력되면 입력이 종료된다.
N으로 0이 입력되면 입력이 종료된다.
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 |}}
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 |}}
