대피소

Time Limit: 3000 msMemory Limit: 1024 MBGold III6Author: 관리자비코week 3

출처: BOJ 28215

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

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

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

입력

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

Problem Statistics

0

Total submissions

0

Accepted

0.0%

Acceptance rate

0

Unique solvers

Silver V3