농부 존의 \(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\)의 최솟값을 출력해야 합니다.
hanzch 1년 전
부하 분산 (Silver)
문제
농부 존의 \(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
예제 출력 1