시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

평면에 N 개의 점이 주어져 있을 때, 이 N 개의 점을 모두 포함하는 가능한 작은 “ 두 개의 직사각형” 을 찾으려 한다. 두 직사각형은 축에 평행하며, 여러분은 두 사각형 중 넓이가 큰 사각형의 넓이를 최소화해야 한다. 

단, 위 그림에서 보는 바와 같이 두 직사각형은 위와 같이 서로 겹치지 않아야 하며 (변 혹은 꼭지점이 서로 접하는 것은 가능하다.) 두 사각형이 같은 모양이거나 같은 넓이를 가질 필요는 없다. 문제는 두 직사각형 중 큰 것의 넓이를 최소화하여 그 넓이를 출력하는 것이다. (참고로 위 그림은 큰 사각형의 넓이를 더 줄일 수 있으므로 정답은 아니다. 아래의 Sample Input/Output 의 두 번째 테스트 케이스를 참조하시오.) 또한, 직사각형은 그 너비 혹은 높이가 0 인 경우도 가능하며, 그런 경우 직사각형의 넓이는 0 이다. 

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 첫 줄에 자연수 N (1 ≤ N ≤ 10000) 이 주어지며, 그 이후 N줄에 N개의 점의 좌표가 두 개의 정수로 한 줄에 주어진다. 좌표값은 모두 정수로 주어지며 -30,000 이상 30,000 이하의 값을 가진다. 주어지는 N개의 점 중에 겹치는 것이 있을 수도 있다. 

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해, 문제에서 요구하는 두 개의 직사각형 중 넓이가 큰 것의 넓이를 출력한다. 

예제 입력

2
2
10 10
20 20
20
0 4
1 1
1 6
2 0
2 2
2 3
2 5
3 4
3 5
4 2
4 3
5 0
5 4
6 2
6 5
7 0
8 1
8 4
10 2
10 4

예제 출력

0
25

힌트