최소최대 삼각분할

복잡한 물체의 응력과 변형을 추정하기 위해, 고체역학의 유한요소법에서는 물체를 압축되지 않는다고 간주하는 작고 단순한 조각들로 분할합니다. 평면을 근사할 때는 단순 다각형을 사용하는 것이 편리합니다. 단순 다각형이란 $m$개의 서로 다른 꼭짓점으로 이루어진, 자기 자신과 교차하지 않는 닫힌 조각별 선형 곡선입니다.

현(chord) 은 다각형의 인접하지 않은 두 꼭짓점을 잇는 선분으로, 다각형 내부에 완전히 포함됩니다. 즉 현이 다각형의 경계와 닿는 점은 두 끝점뿐입니다. 다각형의 삼각분할이란 다각형을 여러 개의 삼각형으로 나누는 $m - 3$개의 현을 선택하는 것입니다. 선택한 현들은 끝점을 제외하고는 서로 교차하지 않으며, 선택하지 않은 나머지 현은 모두 선택된 현 중 적어도 하나와 교차합니다.

임의의 삼각분할을 하나 찾는 것은 쉽습니다. 흥미로운 문제는 주어진 기준에서 가장 좋은 삼각분할을 찾는 것입니다. 이 문제에서 기준은 가장 큰 삼각형의 넓이입니다. 모든 삼각분할 중에서 가장 큰 삼각형이 최대한 작아지는 삼각분할을 찾고, 그 삼각형의 넓이를 구하세요.

그림 1: 예시 다각형이 가질 수 있는 아홉 가지 삼각분할 중 다섯 가지. 맨 왼쪽 것이 가장 큰 삼각형이 가장 작은 삼각분할입니다.

첫째 줄에 시나리오의 개수를 나타내는 양의 정수 $n$이 주어집니다.

각 시나리오의 첫째 줄에는 단순 다각형의 꼭짓점 개수를 나타내는 정수 $m$ ($2 < m < 50$)이 주어집니다. 이어지는 $m$개의 줄에는 각각 꼭짓점의 좌표를 나타내는 두 정수 $x$와 $y$ ($0 \le x \le 10000$, $0 \le y \le 10000$)가 주어집니다. 꼭짓점은 임의의 한 꼭짓점에서 시작하여 시계 방향 또는 반시계 방향으로 경계를 따라 나타나는 순서대로 주어집니다.

각 시나리오마다, 가장 큰 삼각형이 가장 작은 삼각분할에서 그 가장 큰 삼각형의 넓이를 한 줄에 출력합니다. 넓이는 소수점 아래 한 자리까지 출력합니다.

모든 꼭짓점의 좌표가 정수이므로 모든 삼각형의 넓이는 $0.5$의 배수이며, 따라서 답은 항상 정확한 값입니다 (예: 9.0 또는 0.5).