아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

경작지 면적

면접 대비

시간 제한1초메모리 제한128 MB

요약
격자 다각형이 주어질 때 다각형 안에 완전히 들어가는 단위 정사각형의 개수를 센다.
난이도

보통10점 중 6점

유형
기하, 수학, 정수론, 구현
정답자
아직 제출이 없습니다

문제

국무총리가 최근 한 계곡에 있는 값비싼 농경지를 매입하였다. 이 땅은 단위 정사각형 밭들이 규칙적인 격자를 이루는 형태이다. 위원회는 이 거래를 검증하려 하는데, 특히 지불한 가격이 땅의 시장 가치와 일치하는지 확인하려 한다. 시장 가치는 항상 그 땅 안에 완전히 포함되는 단위 정사각형 밭의 개수로 정해진다.

당신의 과제는 이 시장 가치를 계산하는 프로그램을 작성하는 것이다. 매입한 땅은 닫힌 다각형을 이루며, 다각형의 각 꼭짓점은 단위 밭의 모서리, 즉 격자점에 놓여 있다.

예를 들어, 꼭짓점이 (1,1)(1, 1), (5,3)(5, 3), (5,4)(5, 4), (3,5)(3, 5) 인 사각형은 정확히 세 개의 단위 정사각형 밭을 완전히 포함한다.

입력

입력은 여러 개의 시나리오로 이루어진다. 각 시나리오는 다각형 꼭짓점의 개수를 나타내는 정수 NN (3≤N≤1003 \le N \le 100) 이 적힌 줄로 시작한다. 이어지는 NN 개의 줄에는 각각 한 꼭짓점의 좌표를 나타내는 두 정수 XiX_i 와 YiY_i 가 주어진다. 꼭짓점들은 다각형의 경계를 따라 나타나는 순서대로 나열된다. 모든 좌표는 −100≤Xi,Yi≤100-100 \le X_i, Y_i \le 100 을 만족하며, 경계는 자기 자신과 닿거나 교차하지 않는다고 가정해도 된다.

마지막 시나리오 다음에는 00 하나만 있는 줄이 온다.

출력

각 시나리오마다, 다각형 내부에 완전히 포함되는 단위 정사각형의 개수를 정수 하나로 한 줄에 출력한다.

예제4

  1. 예제 1

    입력
    4
    1 1
    5 3
    5 4
    3 5
    5
    3 3
    2 5
    3 4
    5 2
    1 1
    5
    0 0
    0 -50
    -50 -51
    -51 -50
    -50 0
    0
    
    예상 출력
    3
    1
    2500
    
  2. 예제 2

    입력
    4
    0 0
    1 0
    1 1
    0 1
    0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    4
    0 0
    2 0
    2 2
    0 2
    0
    
    예상 출력
    4
    
  4. 예제 4

    입력
    3
    0 0
    4 0
    0 4
    0
    
    예상 출력
    6