다각형 안의 격자 선분 길이

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

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

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

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

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

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

• 3 <= N <= 100000
• -500000000 <= x, y <= 500000000