hanzch   1년 전

부하 분산 (Silver)

시간 제한 메모리 제한
1 초 512 MB

문제

농부 존의 \(N\)마리의 소들은 각각 2차원 농장의 서로 다른 위치 \((x_1, y_1) \ldots (x_N, y_N)\)에 서 있습니다(\(1 \leq N \leq 1000\), 그리고 \(x_i\)와 \(y_i\)는 1,000,000 이하의 양의 홀수입니다). 농부 존은 \(x=a\) 방정식을 가진 남북 방향의 긴(사실상 무한한 길이의) 울타리를 지어 그의 농장을 분할하고 싶어합니다(\(a\)는 짝수여야 하며, 이는 어떤 소의 위치에도 울타리가 지어지지 않도록 보장합니다). 또한 그는 \(y=b\) 방정식을 가진 동서 방향의 긴(사실상 무한한 길이의) 울타리를 짓고 싶어합니다. 여기서 \(b\)도 짝수입니다. 이 두 울타리는 점 \((a,b)\)에서 교차하며, 함께 그의 농장을 네 개의 영역으로 나눕니다.

농부 존은 네 개의 영역에 있는 소들이 적절하게 "균형"을 이루도록, 즉 어떤 영역에도 너무 많은 소가 포함되지 않도록 \(a\)와 \(b\)를 선택하고 싶습니다. \(M\)을 네 영역 중 하나에 있는 소의 최대 수라고 할 때, 농부 존은 \(M\)을 가능한 한 작게 만들고 싶습니다. \(M\)의 가능한 최솟값을 결정하는 것을 도와주세요.

입력

입력의 첫 줄에는 하나의 정수 \(N\)이 주어집니다. 다음 \(N\)개의 줄에는 각각 한 마리의 소의 위치가 주어지며, \(x\)와 \(y\) 좌표가 명시됩니다.

출력

농부 존이 울타리를 최적으로 배치했을 때 얻을 수 있는 \(M\)의 최솟값을 출력해야 합니다.

예제

예제 입력 1

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

예제 출력 1

2

댓글을 작성하려면 로그인해야 합니다.