고전 신화: 평면 나라의 슈퍼히어로
시간 제한1초메모리 제한128 MB
각 점 무리를 모두 포함하는 평행사변형의 최소 넓이를 구한다. 볼록 껍질을 만든 뒤 회전 캘리퍼스로 최소 넓이를 계산한다.
문제
평면 나라(Flatland)에 슈퍼히어로가 필요합니다! 최근 살인 개미 떼가 평면 나라를 습격하고 있지만, 아무도 이 악당들을 막을 방법을 찾지 못하고 있습니다. 다행히 더 높은 차원의 존재인 여러분에게는 평면 나라 주민들의 영웅이 될 기회가 있습니다. 여러분의 임무는 각 개미 떼를 평행사변형 안에 가두어 "얼리는" 것입니다.
각 개미 떼에 대해, 그 떼에 속한 모든 개미를 포함하면서 넓이가 최소인 평행사변형을 찾아야 합니다. 최소 넓이 평행사변형이 개미 떼를 둘러싸면 개미들은 그 자리에 얼어붙어 더 이상 평면의 주민들을 위협할 수 없게 됩니다.
각 개미 떼에 대해 그 떼를 포함하는 최소 넓이 평행사변형의 넓이를 출력하는 프로그램을 작성하세요.
입력
첫째 줄에 개미 떼의 수를 나타내는 정수 ()가 주어집니다.
각 개미 떼는 다음과 같이 주어집니다.
- 한 줄에 그 떼에 속한 개미의 수를 나타내는 정수 ()이 주어집니다.
- 이어지는 개의 줄에 각 개미의 위치가 주어지며, 각 줄에는 공백으로 구분된 두 수 와 (, )가 있습니다.
한 개미 떼 안에서 같은 위치를 차지하는 개미는 없습니다. 각 개미 떼는 서로 독립적으로 처리합니다. 모든 좌표는 소수점 아래 정확히 네 자리를 가지는 고정 소수점 형식(dddd.dddd)으로 주어집니다. 한 개미 떼에 대해 최소 넓이를 이루는 평행사변형이 여러 개 존재할 수 있지만, 구하는 값은 그 최소 넓이 하나뿐이므로 답은 유일합니다.
출력
각 개미 떼에 대해 다음 형식으로 한 줄씩 출력합니다.
Swarm i Parallelogram Area: A
여기서 ()는 개미 떼의 번호이고, 는 그 떼를 포함하는 평행사변형의 최소 넓이입니다. 모든 계산은 64비트 IEEE 부동소수점으로 수행하고, 는 소수점 아래 정확히 네 자리로 반올림하여 고정 소수점 형식으로 출력합니다.