시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 256 MB 113 24 15 23.810%

문제

레프의 부대는 전장에 새 기지를 짓고, 여러 직선 벽으로 구성된 요새와 감시탑으로 이를 둘러싸기로 했다. 두 벽이 만나는 점에는 반드시 감시탑을 설치해야 하고, 전시에 조직적인 움직임을 위해 감시탑은 최대 4개까지만 설치하기로 했다

꼼꼼한 조사 끝에 레프는 탑의 무게를 견딜 수 있고, 시야 확보가 가능한 몇 군데의 점이 감시탑 설치에 적합하다고 판단했다.

프로그래밍을 배운 적이 없는 레프는 가장 넓은 기지를 짓기 위해 여러분에게 가능한 가장 넓은 기지의 넓이를 출력하는 프로그램을 짜  줄 것을 부탁했다. 하지만 정확한 위치는 군사 기밀이기 때문에, 위치는 입력으로만 주어지고, 또한 여러 가짜 데이터 속에 진짜 데이터를 숨길 수 있도록 많은 테스트 케이스를 다룰 수 있어야 한다는 조건을 추가했다. 레프를 만족하게 할 프로그램을 작성해 보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1≤T≤100)가 주어진다.

각각의 테스트 케이스에 대해, 테스트 케이스의 첫 줄에는 감시탑 건설에 적합한 위치의 수 n (3 ≤ n ≤ 1,000)이 주어지며, 이후 n개의 줄에는 감시탑 건설에 적합한 n개의 위치의 x, y좌표가 공백을 사이에 두고 주어진다. 모든 위치의 좌푯값은 모두 다르다.(-10,000 ≤ x, y ≤ 10,000)

출력

각각의 테스트 케이스에 대해, 한 줄에 기지의 최대 넓이를 출력한다. 기지의 넓이가 반정수일 경우 "정수.5"의 형식으로 출력한다. 2.50000과 같이 뒤에 0을 출력할 경우 오답 처리한다.

예제 입력

3
6
0 0
3 7
10 0
11 6
0 10
10 10
5
0 0
-2 -2
3 -2
0 1
0 3
10
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4

예제 출력

100
12.5
31

힌트