레이팅 미적용농부 존의 소 \(N\)마리 (\(5 \leq N \leq 50,000\))가 2차원 들판의 서로 다른 위치에 서 있다. 존은 모든 소를 x축과 y축에 평행한 변을 가진 직사각형 울타리로 둘러싸려 하며, 모든 소를 포함하는 한 이 울타리가 가능한 한 작기를 원한다 (소가 경계 위에 있는 것은 허용된다).
지난 분기 우유 생산량이 저조했던 탓에 존은 안타깝게도 예산이 빠듯하다. 그래서 가능하다면 울타리를 더 작게 만들고 싶어 하며, 이를 위해 소 떼에서 소를 최대 세 마리까지 팔 의향이 있다.
소 떼에서 소를 최대 세 마리까지 제거한 뒤 (그리고 남은 소들을 가장 빈틈없이 둘러싸는 울타리를 지었을 때) 울타리로 둘러쌀 수 있는 최소 넓이를 계산하도록 농부 존을 도와주자.
이 문제에서 소는 점으로, 울타리는 네 개의 선분의 모임으로 취급한다 (즉, 소를 "단위 정사각형"으로 생각하지 않는다). 예를 들어 남은 소들이 모두 하나의 수직선이나 수평선 위에 서 있게 되는 경우처럼, 답이 0이 될 수도 있음에 유의한다.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에 각 소의 위치를 나타내는 두 정수가 주어진다. 소의 위치는 \(1 \ldots 40,000\) 범위의 양의 정수이다.
소 떼에서 신중하게 고른 소를 최대 세 마리까지 제거한 뒤 울타리로 둘러쌀 수 있는 최소 넓이를 나타내는 정수 하나를 출력한다.
reduce.in · 출력을 쓸 파일 reduce.out6
1 1
7 8
10 9
8 12
4 100
50 712riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > US Open > Silver