울타리 치기

들판에 여러 그루의 사과나무가 있다. 모든 사과나무를 포함하는 면적이 가장 작은 직사각형 울타리를 세우려고 한다.

사과나무의 위치는 평면 위의 정수 좌표로 주어진다. 울타리의 네 꼭짓점도 모두 정수 좌표여야 하며, 직사각형의 변이 좌표축과 평행할 필요는 없다.

가능한 울타리가 여러 개라면 출력 규칙에 따라 하나를 고른다.

첫째 줄에 사과나무의 수 n이 주어진다.

다음 n개의 줄에는 각 사과나무의 위치를 나타내는 두 정수 x, y가 주어진다.

n은 1 이상 1,000 이하이고, 모든 x, y는 -20,000 이상 20,000 이하이다.

면적이 가장 작은 직사각형 울타리의 네 꼭짓점을 한 줄에 하나씩 출력한다. 각 줄에는 꼭짓점의 x좌표와 y좌표를 공백으로 구분해 출력한다.

네 꼭짓점은 시계 방향 순서여야 한다. 최소 면적 울타리가 여러 개라면, 가능한 모든 시계 방향 꼭짓점 나열 중 사전순으로 가장 작은 나열을 출력한다. 꼭짓점 하나는 (x, y) 순서로 비교하고, 네 줄의 나열은 앞줄부터 차례대로 비교한다.

최소 면적이 0인 경우에는 가장 멀리 떨어진 두 끝점을 p, q라고 하며, p가 사전순으로 더 작도록 고른 뒤 p, q, q, p 순서로 출력한다.