유리 울타리

상트트베리시에 새로운 주거 지구를 짓기로 했다. 평면상 이 지구는 직사각형 영역이다. 경계와 도로는 동서남북 방향에 정확히 맞춰져 있고, 도로가 지구를 1 km × 1 km 크기의 구역으로 나눈다.

설계도를 실제 지형에 맞춰 보니, 일부 구역이 전부 또는 일부분 습지 위에 놓인다는 사실이 드러났다. 습지는 하나로 이어져 있고, 사방이 개발될 구역들로 둘러싸여 있다. (영역이 이어져 있다는 것은 영역 안의 어떤 점에서든 영역 밖으로 나가지 않고 다른 어떤 점에도 갈 수 있다는 뜻이다.)

지역 생태를 보전하고 주민의 안전을 지키려고 습지를 유리 울타리로 둘러싼다. 울타리는 구역의 경계를 따라서만 세우며, 습지와 필요하면 습지가 아닌 일부 구역을 나머지 지구와 분리한다.

건축 자재를 아끼기 위해 울타리의 길이는 최소여야 한다. 길이가 최소인 울타리들 가운데에서는 울타리 안에 들어가는 지구의 면적이 최소인 울타리를 고른다.

위 조건을 만족하는 울타리를 설계하는 프로그램을 작성하라.

입력 파일에는 습지가 있는 구역들로만 이루어진 영역의 경계를 나타내는 다각형이 주어진다. 다각형의 변은 좌표축과 평행하다.

첫 줄에 정수 n이 주어진다. n은 다각형의 꼭짓점 개수이며, 4 ≤ n ≤ 100000, n은 짝수이다. 이어지는 n개의 줄에는 경계를 반시계 방향으로 따라갈 때의 꼭짓점 좌표가 정수 두 개로 한 줄씩 주어진다. 모든 수의 절댓값은 $10^9$ 이하이다. 경계의 연속한 세 꼭짓점은 한 직선 위에 있지 않다. 경계는 자기 교차나 자기 접촉이 없다.

출력 파일에는 구하는 울타리를 나타내는 다각형을 입력과 같은 형식으로 출력한다. 이 다각형의 연속한 세 꼭짓점은 한 직선 위에 있으면 안 된다.