불 꺼진 헛간

파머 존이 새로 들인 착유기는 전력을 너무 많이 먹어서 헛간의 불이 이따금 꺼진다. 베시는 헛간 지도를 외워 두어서 어두워도 출구까지 갈 수 있지만, 불이 꺼졌을 때 얼마나 더 걸어야 하는지 궁금하다.

헛간은 정수 좌표의 꼭짓점 $(x_1, y_1), \ldots, (x_N, y_N)$을 시계 방향으로 나열한 단순 다각형이다. 경계는 자기 자신과 만나지 않는다. 변은 x축과 나란한 가로변과 y축과 나란한 세로변이 번갈아 나타나며, 첫 변은 둘 중 어느 쪽이어도 된다. 출구는 $(x_1, y_1)$에 있고, 베시는 $i > 1$인 꼭짓점 $(x_i, y_i)$ 중 하나에 서 있다. 베시는 둘레만 따라 시계 방향이나 반시계 방향으로 걷는다. 불이 켜져 있으면 출구까지 더 짧은 쪽으로 걷는다.

불이 꺼지면 베시는 자신이 어느 꼭짓점에 서 있는지 잊어버린다. 지도는 그대로 기억한다. 꼭짓점에 서 있을 때마다, 처음 서 있던 꼭짓점을 포함해서, 그 자리의 내각을 정확히 느끼고 그 꼭짓점이 출구인지 아닌지 안다. 변 하나를 끝까지 걸으면 그 변의 길이를 정확히 알아낸다.

베시의 전략은 정해져 있다. 지금까지 느낀 내각과 변의 길이, 그리고 지나온 꼭짓점 중에 출구가 없었다는 사실을 모두 합쳐 시작 꼭짓점이 하나로 좁혀질 때까지 시계 방향으로 걷는다. 위치를 알아낸 순간 서 있는 꼭짓점에서 출구까지 더 짧은 쪽으로 걷는다. 걷는 도중에 출구에 닿으면 거기서 멈춘다.

시작 꼭짓점을 모두 따졌을 때, 어두울 때 걷는 거리가 불이 켜져 있을 때보다 최대 얼마나 더 긴지 구하라.

첫째 줄에 $N$이 주어진다 ($4 \le N \le 200$). 다음 $N$개 줄에는 헛간의 꼭짓점 좌표 $x_i$와 $y_i$가 시계 방향 순서로 두 정수로 주어진다. 모든 좌표는 $-100000$ 이상 $100000$ 이하이다.

모든 시작 꼭짓점 중에서 어두울 때 더 걷는 거리의 최댓값을 정수 하나로 출력한다. 모든 변이 축과 나란하고 꼭짓점 좌표가 정수이므로 이 값은 정수이다.

예제에서 헛간은 네 꼭짓점이 $(0, 0)$, $(0, 10)$, $(1, 10)$, $(1, 0)$인 직사각형이고 출구는 $(0, 0)$이다. 내각이 모두 90도라서 베시는 처음에 2번, 3번, 4번 꼭짓점을 구분하지 못한다. 세 경우 모두 시계 방향으로 한 변만 걸으면 구분된다.

4번에서 출발하면 길이 1인 변을 걸어 출구에 닿으므로 모두 1만큼 걷고, 이는 불이 켜져 있을 때와 같다. 3번에서 출발하면 길이 10인 변을 걷는데, 이 길이를 가진 후보는 3번뿐이다. 여기서 출구까지는 어느 쪽으로 가도 11이므로 모두 11만큼 걷고, 이 역시 불이 켜져 있을 때와 같다. 2번에서 출발하면 길이 1인 변을 걷고도 출구에 닿지 않는다. 그래서 4번이 아니라 2번에서 출발했다는 사실이 확정된다. 지금 선 자리에서 출구까지는 어느 쪽으로 가도 11이므로 어두울 때는 12를 걷고, 불이 켜져 있으면 10을 걷는다.

가장 나쁜 시작점은 2번이므로 답은 $12 - 10 = 2$이다.