RiseOJ – 울타리 줄이기

설명

농부 존의 소 $$N$$ 마리 ( $3 \leq N \leq 50,000$ )가 2차원 들판의 서로 다른 위치에 서 있다. 존은 모든 소를 x축과 y축에 평행한 변을 가진 직사각형 울타리로 둘러싸려 하며, 모든 소를 포함하는 한 이 울타리가 가능한 한 작기를 원한다 (소가 경계 위에 있는 것은 허용된다).

지난 분기 우유 생산량이 저조했던 탓에 존은 안타깝게도 예산이 빠듯하다. 그래서 가능하다면 울타리를 더 작게 만들고 싶어 하며, 이를 위해 소 떼에서 소 한 마리를 팔 의향이 있다.

소 떼에서 소 한 마리를 제거한 뒤 (그리고 남은 $$N-1$$ 마리의 소를 가장 빈틈없이 둘러싸는 울타리를 지었을 때) 울타리로 둘러쌀 수 있는 최소 넓이를 계산하도록 농부 존을 도와주자.

이 문제에서 소는 점으로, 울타리는 네 개의 선분의 모임으로 취급한다 (즉, 소를 "단위 정사각형"으로 생각하지 않는다). 예를 들어 남은 소들이 모두 하나의 수직선이나 수평선 위에 서 있게 되는 경우처럼, 답이 0이 될 수도 있음에 유의한다. 마지막으로, $$N$$ 이 꽤 클 수 있으므로 프로그램이 충분히 빠르게 동작하도록 풀이 방법에 주의해야 할 수도 있다!

문제 제공: Brian Dean

제약

문제 제공: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 이 주어진다. 다음 $$N$$ 개의 줄에 각 소의 위치를 나타내는 두 정수가 주어진다. 소의 위치는 $1 \ldots 40,000$ 범위의 양의 정수이다.

출력 형식

소 떼에서 신중하게 고른 소 한 마리를 제거한 뒤 울타리로 둘러쌀 수 있는 최소 넓이를 나타내는 정수 하나를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 reduce.in · 출력을 쓸 파일 reduce.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > US Open > Bronze

올림피아드 > USACO > 2015-2016 > US Open > Bronze

태그

JudgeUSACO

울타리 줄이기

평가 및 의견

풀이 제출