다각형 안의 격자 선분 길이

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

요약

정수 좌표를 갖는 단순 다각형이 주어질 때, 다각형 내부에 포함되는 격자선 선분들의 총 길이를 구합니다.

문제

정수 좌표를 꼭짓점으로 가지는 N각형이 무한한 정사각 격자 위에 놓여 있다. 이 다각형은 단순 다각형이다. 즉, 이웃한 두 변은 하나의 공통 꼭짓점만 공유하고, 이웃하지 않은 두 변은 서로 만나거나 닿지 않는다.

격자의 모든 세로선과 가로선 중 다각형의 내부에 포함되는 부분들의 길이를 모두 더한 값을 구하라. 다각형의 경계 위에만 놓인 부분은 내부 길이에 포함하지 않는다.

첫째 줄에 꼭짓점의 개수 N이 주어진다. 다음 N개의 줄에는 각 꼭짓점의 좌표를 나타내는 두 정수 x와 y가 주어진다.

꼭짓점은 시계 방향 또는 반시계 방향 순서로 주어지며, 모든 꼭짓점은 서로 다르다.

첫째 줄에 다각형 내부에 포함되는 격자 선분 길이의 합을 출력한다.

정답과의 절대 오차 또는 상대 오차가 10^-6 이하이면 정답으로 인정된다.