백준 17371 - 이사 [Python]

www.acmicpc.net/problem/17371

17371번: 이사

편의시설을 집으로 쓸 수 없다는 조건이 없기 때문에, 문제가 매우 쉬워졌다.

그냥 편의시설을 집으로 쓰면 된다.

 

집과 가장 가까운 편의시설의 거리는 0이 되므로, 가장 먼 편의시설과의 거리만 계산해주면 O(N^2)에 풀 수 있다. N제한도 1000밖에 되지 않아 충분하다!

집을 편의시설로 정하는게 왜 되는건지는 직접 증명해보세요. 절대 제가 귀찮아서가 아닙니다

 

주석으로 코드에 대한 설명을 해두었다.

import sys
input = sys.stdin.readline
 
MAX = 10**12
a = []
 
def d(a1,a2): # 두 점 사이의 거리
    return (a1[0] - a2[0])**2 + (a1[1] - a2[1])**2
 
n = int(input())
for i in range(n):
    a.append(list(map(int, input().split())))
 
ans = [MAX, 0] # [거리, 인덱스]
for i in range(n): # 가장 가까운 편의시설: a[i]
    m = 0
    for j in range(n): # 가장 먼 편의시설을 찾음
        if i == j: continue
 
        m = max(m, d(a[i], a[j]))
    if m < ans[0]: # ans 갱신
        ans = [m, i]
 
print(a[ans[1]][0], a[ans[1]][1])

 

아 블루 언제가지 ㅋㅋ