미술관

발칸 협력 센터의 미래지향적인 새 건물에 있는 미술관들은 (볼록하지 않을 수도 있는) 다각형 모양입니다. 큰 전시회가 열리면 모든 그림을 감시하는 일이 중요한 보안 과제가 됩니다.

주어진 미술관에 대해, 미술관 벽의 모든 점이 보이는 바닥 영역의 넓이를 구하는 프로그램을 작성하세요. 바닥의 한 점과 벽의 한 점을 잇는 선분이 미술관 내부에 완전히 들어 있을 때 그 벽의 점이 보인다고 하며, 따라서 경계 전체를 한 번에 볼 수 있는 영역의 넓이를 구해야 합니다.

그림 1은 어떤 좌표계에서 미술관의 지도를 보여 주고, 넓이를 구해야 하는 영역은 그림 2에 음영으로 표시되어 있습니다.

첫 번째 줄에는 처리해야 할 작업의 수 T가 주어집니다. 각 작업은 미술관 다각형의 꼭짓점 개수인 정수 N (5 ≤ N ≤ 1500)이 적힌 줄로 시작합니다. 이어지는 N개의 줄에는 각각 한 꼭짓점의 좌표가 주어지며, 16비트 정수형에 들어가는(즉, −32768부터 32767까지의) 두 정수가 공백 하나로 구분되어 있습니다. 꼭짓점들은 다각형 경계를 따라 순서대로 나열됩니다. 한 작업의 마지막 꼭짓점 바로 다음에 같은 형식으로 다음 작업이 이어집니다.

각 작업마다 구한 넓이를 소수점 아래 정확히 두 자리(가장 가까운 100분의 1로 반올림)로 한 줄에 출력하세요.