정올 대피소

from itertools import combinations
N, K = map(int,input().split())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int,input().split())

INF  = float("INF")

def fun(c):
    b=0
    for h_idx in range(N):
        a=INF
        for c_idx in c:
            tmp = abs(x[h_idx]-x[c_idx])+abs(y[h_idx]-y[c_idx])
            a = min(a,tmp)
        b = max(b, a)
    return b 

result = INF
for c in combinations(range(N),K):
    result = min(result,fun(c))
print(result)

이 코드는 N개의 좌표 중 K개를 선택해서 기준점으로 삼을 때, 나머지 모든 점들이 이 기준점들 중 가장 가까운 점과의 거리 중 최대값이 최소가 되도록 하는 값을 구하는 프로그램이다. 먼저 모든 좌표를 입력받고, combinations를 이용해 N개 중 K개를 선택하는 모든 경우를 만든다. 각 조합에 대해 fun 함수는 모든 점에서 가장 가까운 기준점까지의 거리를 계산하고, 그 거리들 중 가장 먼 거리를 반환한다. 이렇게 구한 거리들 중 가장 작은 값을 최종적으로 출력한다. 즉, 최적의 K개 기준점을 선택해 전체 최대 거리를 최소화하는 문제다.