욱제는 건축왕이야!!
면접 대비시간 제한2초메모리 제한512 MB
축에 나란한 변으로 이루어진 직교 볼록 다각형의 꼭짓점이 순서대로 주어질 때 둘레의 길이를 구한다.
문제
건축학개론을 수강한 욱제는 선린의 매점 앞에 지어질 새 건물의 설계를 맡았다. 욱제는 건축학개론 수업에서 수지를 만나 행복하지만, C-를 받을 정도로 건축에 소질이 없다.
컴퓨터학부에 재학 중인 욱제는 이 건물의 설계도를 그림이 아니라 선분과 선분이 만나는 꼭짓점들의 좌표로 관리한다. 이 설계도는 건물 바닥 부분만을 나타낸 밑면도(저면도)이다. 하지만 프로그래밍도 C-인 욱제는 자신이 설계한 건물의 둘레를 구할 방법을 찾지 못해 발을 동동 구르고 있다.
욱제가 설계한 건물은 어느 방향에서 보아도 가운데가 파인 부분이 없는 직각으로 볼록한 닫힌 곡선 모양이다. 단순한 타원을 디지털화한 모양이라고 할 수 있겠다. 욱제의 설계도는 2차원 좌표평면 위의 격자에 꼭 맞게 표현된다. (이런 모양을 영어로는 orthogonally convex rectilinear polygon이라고 한다)
욱제는 당신에게 밑면도의 모든 꼭짓점 좌표를 넘겨주며 도움을 요청했다. 설계도는 욱제가 넘겨주는 좌표 순서대로 i번째 좌표와 i+1번째 좌표를 잇는 선분을 그려 복원할 수 있다. N번째 좌표는 1번째 좌표와 이어지며 선분은 항상 격자에 맞게 주어진다.
욱제를 대신해 이 건물의 둘레를 구하고 건축학개론의 주인공 자리를 빼앗자!
입력
첫째 줄에 꼭짓점의 개수 N이 주어진다. (4 ≤ N ≤ 20)
이후 둘째 줄부터 N개의 줄에 걸쳐 꼭짓점의 좌표 (x, y)가 주어진다. 좌표는 40 이하의 음이 아닌 정수이며, 중복되는 좌표는 주어지지 않는다.
출력
욱제가 설계한 건물의 둘레의 길이를 출력한다.