대피소

시간 제한: 3000 ms메모리 제한: 1024 MBGold III6작성자: 관리자비코week 3

출처: BOJ 28215

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

i번째 집과 j번째 집 사이의 거리는 |Xᵢ - Xⱼ| + |Yᵢ - Yⱼ|이다 (맨해튼 거리).

KOI 마을은 재난 발생 시 주민들이 안전하게 대피할 수 있도록 K개의 집에 대피소를 설치할 계획이다. 모든 주민의 안전을 위해 각 집에서 가장 가까운 대피소까지의 거리 중 최댓값을 최소화하고자 한다.

입력

첫 번째 줄에 N과 K가 공백을 사이에 두고 주어진다.
다음 N개의 줄에는 집의 위치가 주어지는데, i번째 줄에는 Xᵢ와 Yᵢ가 공백을 사이에 두고 주어진다.

문제 통계

0

전체 제출

0

정답

0.0%

정답률

0

정답자 수

비슷한 문제

출력

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

Silver V3