부하 분산

농부 존의 소 \(N\)마리가 2차원 농장의 서로 다른 위치 \((x_1, y_1) \ldots (x_n, y_n)\)에 각각 서 있다 (\(1 \leq N \leq 100,000\), \(x_i\)와 \(y_i\)는 최대 \(1,000,000\)인 양의 홀수 정수). 농부 존은 방정식 \(x=a\)인 긴(사실상 무한한 길이의) 남북 방향 울타리를 세워 밭을 나누고 싶다 (\(a\)는 짝수 정수이므로 어떤 소의 위치도 울타리가 지나가지 않는다). 또한 \(b\)가 짝수 정수일 때 방정식 \(y=b\)인 긴(사실상 무한한 길이의) 동서 방향 울타리도 세우려 한다. 두 울타리는 점 \((a,b)\)에서 교차하며, 함께 밭을 네 영역으로 나눈다.

농부 존은 네 영역에 나타나는 소들이 어느 정도 "균형"을 이루어, 어느 영역에도 소가 너무 많지 않도록 \(a\)와 \(b\)를 정하고 싶다. 네 영역 중 한 영역에 나타나는 소의 최대 수를 \(M\)이라 할 때, 농부 존은 \(M\)을 최대한 작게 만들고 싶다. 이 \(M\)의 가능한 최솟값을 구하는 것을 도와주자.

출제자: Brian Dean

출제자: Brian Dean

입력의 첫째 줄에 정수 \(N\)이 하나 주어진다. 다음 \(N\)개의 줄에 소 한 마리의 위치가 \(x\)와 \(y\) 좌표로 각각 주어진다.

농부 존이 울타리를 최적으로 배치했을 때 달성할 수 있는 \(M\)의 가능한 최솟값을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > February > Platinum