\(2\)차원 평면의 KOI 마을에 \(N\)개의 집이 있다. 각 \(i\)번째 집의 위치는 \((X_i , Y_i)\)이다.

\(i\)번째 집과 \(j\)번째 집 사이의 거리는 \(|X_i - X_j | + |Y_i - Y_j |\)이다. 즉, 두 집 사이의 거리는 \(X\)의 차이와 \(Y\)의 차이의 합이다. 예를 들어, \((1, 6)\)에 위치한 집과 \((2, 4)\)에 위치한 집은 \((2 - 1) + (6 - 4)\)인 \(3\)만큼 떨어져 있다.

KOI 마을은 재난 발생 시 주민들이 안전하게 대피할 수 있도록 \(K\)개의 집에 대피소를 설치할 계획이다. 모 든 주민의 안전을 고려하여, 집에서 가장 가까운 대피소로 이동할 때 가장 긴 거리가 최소가 되도록 대피소를 설치할 \(K\)개의 집을 선택하고, 그때 대피소와 가장 멀리 떨어진 집과의 거리를 구하려고 한다.

아래는 \(5\)개의 집이 각각 \((1, 5)\), \((3, 0)\), \((3, 3)\), \((6, 12)\), \((8, 9)\)에 위치한 마을의 예이다.

이 마을에 \(2\)개의 대피소를 설치하려고 한다. 만약 \((3, 0)\)과 \((1, 5)\)에 위치한 집에 대피소를 설치한다면 설치하지 않은 나머지 세 집에서 가까운 대피소까지의 거리가 각각 \(3\), \(11\), \(12\)이고, 이 중 가장 먼 거리는 \(12\)이다.

하지만 \((3, 3)\)와 \((6, 12)\)에 위치한 집에 대피소를 설치하면 가장 가까운 대피소와 가장 멀리 떨어져 있는 집은 \((8, 9)\)에 위치한 집으로, \((6, 12)\)와 \(5\)만큼 떨어져 있다. 대피소를 어떻게 설치해도 최대 거리가 \(5\)보다 작아지는 경우가 없으므로 \(5\)가 구하고자 하는 거리가 된다.

KOI 마을의 집들의 위치와 설치할 대피소의 개수가 주어질 때, 대피소를 설치하는 모든 방법 중 가장 가까운 대피소와 집 사이의 거리 중 가장 큰 값이 가장 작을 때의 거리를 구해라.

• 주어지는 모든 수는 정수이다.
• \(1 \le K \le 3\)
• \(K \le N \le 50\)
• \(0 \le X_i \le 100\,000\)
• \(0 \le Y_i \le 100\,000\)
• 같은 위치에 집이 여럿 존재하지 않는다. 즉, \((X_1, Y_1), (X_2, Y_2), \cdots, (X_N, Y_N)\)는 서로 다르다.

첫 번째 줄에 \(N\)과 \(K\)가 공백을 사이에 두고 주어진다.

다음 \(N\)개의 줄에는 집의 위치가 주어지는데, 이 중 \(i\) (\(1 ≤ i ≤ N\))번째 줄에는 \(X_i\)와 \(Y_i\)가 공백을 사이에 두고 주어진다.

첫 번째 줄에 답을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 1차 대회 > 초등부 2번 / 고등부 1번