소풍

내일 회사의 연례 소풍이 Gloomwood 공원에서 열린다. 준비를 맡은 사람은 모두가 서로를 바라볼 수 있는 자리를 원한다. 그러려면 고른 영역이 볼록(convex) 해야 한다. 즉, 영역 안의 임의의 두 점을 잇는 선분이 영역 안에 완전히 포함되어야 한다.

공원에는 큰 나무나 바위처럼 시야를 가리는 불투명한 장애물이 많다. 각 장애물은 크기가 없는 하나의 점으로 본다. 영역은 몇몇 장애물을 감싸도록 리본을 둘러 표시하므로, 영역의 꼭짓점은 모두 장애물이다. 모두가 서로를 볼 수 있으려면 어떤 장애물도 영역 내부에 놓여서는 안 된다(경계 위에 있는 장애물은 허용된다).

꼭짓점이 모두 장애물이고 내부에 어떤 장애물도 포함하지 않는 볼록 다각형 중에서 넓이가 가장 큰 것을 찾아라.

위에서 내려다본 공원. 검은 점은 장애물이고, 점선은 소풍 영역이다.

첫 줄에 시나리오의 수 $n$(양의 정수)이 주어진다.

각 시나리오는 두 줄로 이루어진다. 첫 줄에는 장애물의 수 $m$ ($2 < m < 100$)이 주어진다. 둘째 줄에는 장애물의 좌표가 $x_1\ y_1\ x_2\ y_2\ \dots\ x_m\ y_m$ 순서로 주어진다. 모든 좌표는 $[0, 1000]$ 범위의 정수다. 각 시나리오에는 한 직선 위에 있지 않은 장애물이 적어도 셋 있으며, 좌표가 같은 두 장애물은 없다.

각 시나리오마다, 꼭짓점이 모두 장애물이고 내부에 장애물을 포함하지 않는 가장 큰 볼록 다각형의 넓이를 소수점 아래 한 자리까지 한 줄에 출력한다.