[고등부] 2025 KOI 2차대회 대비 모의고사 (2회차)

N명의 국민은 각각 나라의 2차원 평면에서 서로 다른 위치 (x_1, y_1), ..., (x_N, y_N)에 살고 있다.
(모든 국민의 위치는 홀수 정수로만 구성된다)

국가의 왕은 국가를 네 개의 도시로 나누고 싶다.

이에 왕은 우선 x=a라는 방정식을 가진 남북 방향의 울타리를 세우고 싶어 한다.

여기서 a는 짝수 정수로 설정하여 사람들의 집을 허물지 않도록 한다.

그는 또한 y=b라는 방정식을 가진 동서 방향의 울타리도 세우고 싶어 하는데, 여기서 b 역시 짝수 정수다.

이 두 울타리는 (a,b)라는 점에서 교차하며, 함께 국가를 네 개의 도시로 나눈다.

왕은 적절한 두 정수 a와 b를 선택하여 네 개의 도시에 거주하는 국민의 수가 적절하게 "균형"을 이루도록 하고 싶다.

한 도시에 있는 국민의 수가 너무 많지 않도록 하기 위해 M을 정의하는데,
여기서 M은 네 개의 도시 중 가장 많은 국민이 살고 있는 지역의 국민의 수다.

왕은 M을 가능한 한 작게 만들기를 원한다.

최적의 울타리 위치를 찾아 왕이 달성할 수 있는 가장 작은 값 M을 계산하는 데 도움을 주자.