고전 신화: 평면 나라의 슈퍼히어로

시간 제한1초메모리 제한128 MB

문제

평면 나라(Flatland)에 슈퍼히어로가 필요합니다! 최근 살인 개미 떼가 평면 나라를 습격하고 있지만, 아무도 이 악당들을 막을 방법을 찾지 못하고 있습니다. 다행히 더 높은 차원의 존재인 여러분에게는 평면 나라 주민들의 영웅이 될 기회가 있습니다. 여러분의 임무는 각 개미 떼를 평행사변형 안에 가두어 "얼리는" 것입니다.

각 개미 떼에 대해, 그 떼에 속한 모든 개미를 포함하면서 넓이가 최소인 평행사변형을 찾아야 합니다. 최소 넓이 평행사변형이 개미 떼를 둘러싸면 개미들은 그 자리에 얼어붙어 더 이상 평면의 주민들을 위협할 수 없게 됩니다.

각 개미 떼에 대해 그 떼를 포함하는 최소 넓이 평행사변형의 넓이를 출력하는 프로그램을 작성하세요.

입력

첫째 줄에 개미 떼의 수를 나타내는 정수 $s$ ($1 \le s \le 20$)가 주어집니다.

각 개미 떼는 다음과 같이 주어집니다.

  • 한 줄에 그 떼에 속한 개미의 수를 나타내는 정수 $n$ ($4 \le n \le 1000$)이 주어집니다.
  • 이어지는 $n$개의 줄에 각 개미의 위치가 주어지며, 각 줄에는 공백으로 구분된 두 수 $x$와 $y$ ($-1000 \le x \le 1000$, $-1000 \le y \le 1000$)가 있습니다.

한 개미 떼 안에서 같은 $(x, y)$ 위치를 차지하는 개미는 없습니다. 각 개미 떼는 서로 독립적으로 처리합니다. 모든 좌표는 소수점 아래 정확히 네 자리를 가지는 고정 소수점 형식(dddd.dddd)으로 주어집니다. 한 개미 떼에 대해 최소 넓이를 이루는 평행사변형이 여러 개 존재할 수 있지만, 구하는 값은 그 최소 넓이 하나뿐이므로 답은 유일합니다.

출력

각 개미 떼에 대해 다음 형식으로 한 줄씩 출력합니다.

Swarm i Parallelogram Area: A

여기서 $i$ ($1 \le i \le s$)는 개미 떼의 번호이고, $A$는 그 떼를 포함하는 평행사변형의 최소 넓이입니다. 모든 계산은 64비트 IEEE 부동소수점으로 수행하고, $A$는 소수점 아래 정확히 네 자리로 반올림하여 고정 소수점 형식으로 출력합니다.