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

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

요약
각 점 무리를 모두 포함하는 평행사변형의 최소 넓이를 구한다. 볼록 껍질을 만든 뒤 회전 캘리퍼스로 최소 넓이를 계산한다.
난이도

어려움10점 중 8점

유형
기하, 분할 정복, 수학, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

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

출력

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

Swarm i Parallelogram Area: A

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

예제2

  1. 예제 1

    입력
    2
    6
    0.0000 0.0000
    -0.5000 -0.5000
    -1.0000 0.0000
    -0.7000 -7.0000
    -1.0000 -1.0000
    0.0000 -1.0000
    5
    2.0000 2.0000
    0.0000 0.0000
    0.5000 2.0000
    1.0000 1.0000
    1.5000 0.0000
    
    예상 출력
    Swarm 1 Parallelogram Area: 7.0000
    Swarm 2 Parallelogram Area: 3.0000
    
  2. 예제 2

    입력
    1
    4
    0.0000 0.0000
    2.0000 0.0000
    2.0000 2.0000
    0.0000 2.0000
    
    예상 출력
    Swarm 1 Parallelogram Area: 4.0000