#1755 직사각형 만들기

10 s   128 MB  

Description

이 문제에선 2차원 좌표계 상의 N개의 정수 좌표의 점들이 주어진다.

이 중에서 4개의 점을 선택 하여 이들이 직사각형의 꼭지점이 될 때, 가장 큰 면적을 가지는 경우를 구하는 프로그램을 작성하라.
 
입력은 항상 직사각형을 만들 수 있는 경우로 주어진다고 가정한다.
 

Input

입력은 여러개의 테스트 케이스로 이뤄지며, 첫 줄에 테스트 케이스의 개수 T가 주어진다.

테스트 케이스의 첫째 줄에는 4이상 1,500 이하의 정수 N이 주어진다. 
그 다음줄 부터 N개의 줄에 -108이상 108이하의 정수인 각 점의 xy의 좌표값이 주어진다.
 

Output

각 테스트 케이스에 대해 문제의 조건을 만족하여 만들 수 있는 가장 큰 직사각형의 넓이를 한줄에 출력한다.

Sample Input

Sample Output

1
8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1
10

HINT

다음은 입력 예시에 주어진 테스트 케이스를 그림으로 표현한 것이다.

Source

BOI 2009