파일 업로드

영역 축소

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

학교의 NN명의 학생들 (3N50,0003 \leq N \leq 50,000)은 모두 교내의 다양한 위치에 있습니다. 철수는 모든 학생을 포함하는 직사각형 형태의 영역으로 나누려고 합니다. 이 영역의 변은 x와 y축에 평행해야 합니다. 그리고 철수는 이 영역이 최대한 작게 만들고 싶어합니다(경계선에 있는 학생들도 포함됩니다).

그러나 지난 학기 동안 학생들의 성적이 좋지 않았기 때문에 철수는 예산이 매우 타이트합니다. 그래서 가능하다면 더 작은 영역을 만들고자 합니다. 철수는 이를 위해 한 명의 학생을 학교에서 퇴학시키려고 합니다.

철수가 학교에서 한 학생을 퇴학시킨 후, 남은 N1N-1명의 학생들을 포함하는 가장 작은 영역의 넓이를 계산해주세요.

이 문제에서는 학생들을 점으로, 영역을 4개의 선분으로 생각합니다. 답이 0이 될 수도 있습니다. 예를 들면, 남은 모든 학생들이 동일한 수직 또는 수평선상에 위치할 경우입니다. 마지막으로, NN이 꽤 크기 때문에 프로그램이 충분히 빠르게 실행되도록 문제를 해결하는 방법에 신경 써야할 수 있습니다.

💻 입력

첫 번째 입력 줄에는 NN이 포함됩니다. 다음 NN 줄 각각은 학생의 위치를 나타내는 두 개의 정수를 포함합니다. 학생의 위치는 140,0001 \ldots 40,000 범위의 양의 정수입니다.

🖨️ 출력

철수가 학교에서 학생 중 하나를 퇴학시킨 후, 만들 수 있는 최소 영역의 넓이를 한 정수로 작성해주세요.


💻 예제 입력 1
4
2 4
1 1
5 2
17 25
🖨️ 예제 출력 1
12

출처: USACO 2016 US Open Contest, Bronze Problem 3. Field Reduction