문제
평면에 N개의 점이 주어져 있을 때, 이 N개의 점을 보두 포함하는 가능한 작은 2개의 직사각형을 찾으려 한다.
두 개의 직사각형은 축에 평행하며, 이 두 사각형 중 넓이가 큰 사각형의 넓이를 최소화해야 한다.
단, 위 그림에서 보는 바와 같이 두 직사각형은 위와 같이 서로 겹치지 않아야 하며 (변 혹은 꼭지점 역시 접하면 안된다.) 두 사각형이 같은 모양이거나 같은 넓이를 가질 필요는 없다.
문제는 두 직사각형 중 큰 것의 넓이를 최소화 하여 그 넓이를 출력하는 것이다. 또한, 직사각형은 그 너비 혹은 높이가 0인 경우도 가능하며, 그런 경우 직사각형의 넓이는 0이다.
입력
입력의 첫 줄에는 점의 개수 N(1≤N≤10,000)이 주어지며, 그 이후 N개의 줄에 N개의 점의 좌표가 두 개의 정수로 한줄에 주어진다. 좌표값은 모두 정수로 주어지며, -3,000,000 이상 3,000,000이하의 값을 가진다. 주어지는 점은 X좌표와 Y좌표가 겹치는 점은 없다고 가정한다.
출력
입력에 대해서 문제에서 요구하는 두 개의 직사각형 중 넓이가 큰 것의 넓이를 출력한다.
예제
4
1 1
2 3
3 4
5 -1
6
로그인해야 코드를 작성할 수 있어요.