시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 39 13 9 75.000%

문제

N개의 꼭지점을 가진 단순 다각형 (Simple Polygon)이 무한한 사각 격자판에 그려져 있다. 단순 다각형은, 두 개의 인접한 변이 오직 하나의 공통된 꼭지점을 지나고, 이러한 변이 아니라면 교차하거나, 접하지 않는다. 모든 꼭지점은 정수 좌표를 가진다.

이러한 다각형이 주어지면, 다각형 내부에 격자 선분의 길이를 구하면 된다. (그림 참고)

입력

첫째 줄에 꼭지점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 두 정수 x와 y가 주어진다. 이 좌표는 하나의 꼭지점이다. 꼭지점은 시계방향 또는 반시계 방향으로 주어지며, 모든 꼭지점은 서로 다르다. (3<=N<=100,000, -500,000,000<=x,y<=500,000,000)

출력

첫째 줄에, 다각형 내부의 격자 선분의 길이를 출력하면 된다.

정답과의 절대/상대 오차는 10-3까지 허용된다.

예제 입력

3
5 1
2 4
1 1

예제 출력

10.0

힌트

 

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 7번