가장 큰 사각형
시간 제한6초메모리 제한1024 MB
정수 좌표의 점이 최대 4096개 주어질 때, 그중 네 점을 꼭짓점으로 하는 사각형의 최대 넓이를 구합니다.
문제
2차원 유클리드 평면 위에 주어진 여러 점들 중에서 꼭짓점이 주어진 점들에 속하는 사각형의 최대 넓이를 구하시오. 예를 들어 점 A(0, 0), B(1, 0), C(3, 1), D(1, 2), E(0, 1)이 주어졌다고 하자. 이 점들로는 ABCD, ABCE, ABDE, ACDE, BCDE의 단순 사각형 5개가 만들어지며, 넓이는 각각 3, 2, 1.5, 3, 3이다. 또 ABDC, ABEC, ABED, ACED, BCED, ACBD, ACBE, ADBE, ADCE, BDCE의 꼬인 사각형 10개가 있는데, 이들의 넓이는 더 작다. 따라서 최대 넓이는 3이다.
그림 4: 모든 사각형 중에서 BCDE의 넓이가 3으로 최대이다.
주어진 점들에는 같은 점이 중복되어 나타날 수 있다. 퇴화된 경우도 사각형으로 취급한다. 예를 들어 A(0, 0), B(0, 0), C(0, 0), D(0, 0)으로 이루어진 사각형 ABCD도 유효하다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다. 이어지는 N개의 줄에는 점의 좌표를 나타내는 정수 X와 Y가 각각 주어진다.
출력
각 테스트 케이스마다 주어진 점들을 꼭짓점으로 하는 사각형 중 최대 넓이를 출력한다.
제한
- 지수 표기법으로 출력하면 안 된다. 예를 들어 300000000을 3E8로 출력하면 안 된다.
- 넓이는 불필요한 문자 없이 출력한다. 예를 들어 3을 3.0으로 출력하면 틀렸다.
- 시간 제한은 6000 ms이고, 메모리 제한은 1024 MB이다.