골프장 부지

문어 교수는 예전에 골프장으로 쓰던 넓은 땅을 소유한다. 이 땅에는 골프공이 빠지던 홀이 아직 많이 남아 있다. 문어 교수는 땅의 일부를 정해진 값에 팔겠다고 제안했다. 파는 부분은 이렇게 정한다. 당신이 홀 네 개를 고르면, 고른 홀의 볼록 껍질이 둘러싸는 만큼을 받는다. 고른 홀의 볼록 껍질은 고른 홀을 모두 내부나 경계에 포함하는 가장 작은 볼록 다각형이다. 땅의 질은 어디나 같으므로, 볼록 껍질의 넓이가 최대가 되도록 홀 네 개를 고르려고 한다.

그림 1

예를 들어 그림 1 (a)에는 땅에 있는 홀 여덟 개가 그려져 있다. 여기서 검은 점으로 표시한 홀 1, 3, 5, 8을 골랐다고 하자. 이 네 홀을 꼭짓점으로 하는 사각형은 어떻게 이어도 볼록하지 않다. 그래서 네 홀의 볼록 껍질은 그림처럼 홀 1, 3, 8을 꼭짓점으로 하는 삼각형이다. 또 이 삼각형이 홀 네 개로 만들 수 있는 모든 볼록 껍질 가운데 가장 넓다는 것도 어렵지 않게 알 수 있다. 그림 1 (b)는 홀이 여덟 개인 다른 땅이다. 이 예에서 가장 넓은 볼록 껍질은 홀 1, 3, 5, 8을 꼭짓점으로 하는 볼록사각형이다.

평면 위의 점 $n$개로 이루어진 집합 $P$가 주어진다. $P$의 점 네 개로 만들 수 있는 볼록 껍질의 넓이 가운데 최댓값을 구하는 프로그램을 작성하시오.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 집합 $P$의 점 개수 $n$이 주어지며, $4 \le n \le 30000$이다. 다음 줄에는 정수 $2n$개가 $x_1\ y_1\ x_2\ y_2 \dots x_n\ y_n$ 순서로 주어진다. $x_i$와 $y_i$는 점 $p_i$의 x좌표와 y좌표다. 좌표는 모두 정수이고 $-10^9 \le x_i \le 10^9$, $-10^9 \le y_i \le 10^9$이다. 한 직선 위에 점이 세 개 이상 놓이는 경우는 없다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 $P$의 점 네 개로 만들 수 있는 볼록 껍질의 넓이 중 최댓값을 소수점 아래 첫째 자리까지 한 줄에 하나씩 출력한다. 좌표가 모두 정수이므로 넓이는 항상 $0.5$의 배수이고, 소수점 아래 첫째 자리는 0 또는 5다.