레이팅 미적용설명
농부 존의 소 \(N\)마리(\(3 \leq N \leq 50,000\))가 2차원 목장의 서로 다른 위치에 있다. 존은 변이 x축과 y축에 평행한 직사각형 울타리로 모든 소를 둘러싸려고 하며, 모든 소를 포함하는 한(경계 위의 소도 허용된다) 이 울타리를 가능한 한 작게 만들고 싶어 한다.
안타깝게도 존은 지난 분기 우유 생산량이 저조해 예산이 빠듯하다. 그래서 유지 비용을 줄이기 위해 더 작은 넓이를 둘러싸고 싶은데, 그가 생각해 낸 유일한 방법은 울타리를 하나 대신 두 개 만드는 것이다. 울타리를 하나 대신 두 개 사용함으로써 총 얼마만큼의 넓이를 덜 둘러쌀 수 있는지 계산해 존을 도와주자. 원래의 울타리와 마찬가지로, 두 울타리는 합쳐서 모든 소를 포함해야 하고(경계 위의 소도 허용된다), 변이 x축과 y축에 평행해야 한다. 두 울타리는 겹칠 수 없으며, 경계끼리도 닿을 수 없다. 넓이가 0인 울타리도 허용된다는 점에 유의한다. 예를 들어 너비가 0이거나 높이가 0인 울타리도 가능하다.
문제 출제: 브라이언 딘(Brian Dean)
제약
문제 출제: 브라이언 딘(Brian Dean)
입력 형식
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 각 소의 위치를 나타내는 두 정수가 주어진다. 소의 좌표는 \(1 \ldots 1,000,000,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:
입력을 읽을 파일
split.in · 출력을 쓸 파일 split.out예제 1
입력
6
4 2
8 10
1 1
9 12
14 7
2 3출력
107문제 정보
태그