실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
학교의 명의 학생들 ()은 모두 교내의 다양한 위치에 있습니다. 철수는 모든 학생을 포함하는 직사각형 형태의 영역으로 나누려고 합니다. 이 영역의 변은 x와 y축에 평행해야 합니다. 그리고 철수는 이 영역이 최대한 작게 만들고 싶어합니다(경계선에 있는 학생들도 포함됩니다).
그러나 지난 학기 동안 학생들의 성적이 좋지 않았기 때문에 철수는 예산이 매우 타이트합니다. 그래서 가능하다면 더 작은 영역을 만들고자 합니다. 철수는 이를 위해 한 명의 학생을 학교에서 퇴학시키려고 합니다.
철수가 학교에서 한 학생을 퇴학시킨 후, 남은 명의 학생들을 포함하는 가장 작은 영역의 넓이를 계산해주세요.
이 문제에서는 학생들을 점으로, 영역을 4개의 선분으로 생각합니다. 답이 0이 될 수도 있습니다. 예를 들면, 남은 모든 학생들이 동일한 수직 또는 수평선상에 위치할 경우입니다. 마지막으로, 이 꽤 크기 때문에 프로그램이 충분히 빠르게 실행되도록 문제를 해결하는 방법에 신경 써야할 수 있습니다.
첫 번째 입력 줄에는 이 포함됩니다. 다음 줄 각각은 학생의 위치를 나타내는 두 개의 정수를 포함합니다. 학생의 위치는 범위의 양의 정수입니다.
철수가 학교에서 학생 중 하나를 퇴학시킨 후, 만들 수 있는 최소 영역의 넓이를 한 정수로 작성해주세요.
4 2 4 1 1 5 2 17 25
12
출처: USACO 2016 US Open Contest, Bronze Problem 3. Field Reduction