이번 문제는 그리디 알고리즘을 통해 해결하였다. 처음에는 예제에서 보여주는 출력값을 구하는 방법을 도저히 생각할 수가 없었다. 그래서 다른 사람의 풀이를 찾아보았고, 오차가 10-6 이하면 인정한다는 말을 이용하면 간단하게 볼 수 있다는 사실을 알게 되었다. 편의시설과 같은 위치에도 집을 지을 수 있기 때문에 편의시설과 같은 위치로 이사한다고 생각할 수 있다. 이렇게 되면 가장 가까운 편의시설의 거리는 0이 되고, 이 과정을 반복하며 가장 먼 편의시설의 거리가 가장 짧은 경우를 구하면 되는 문제이다. 이러한 방식으로 정답을 구할 수 있었다.

Code

n = int(input())
conv = [tuple(map(int, input().split())) for _ in range(n)]
def get_dist(y1, x1, y2, x2):
    return (y1-y2)**2 + (x1-x2)**2
min_dist = 1e9
min_idx = -1
for i in range(n):
    max_dist = 0
    max_idx = 0
    for j in range(n):
        dist = get_dist(conv[i][0], conv[i][1], conv[j][0], conv[j][1])
        if dist > max_dist:
            max_dist = dist
            max_idx = i
    if max_dist < min_dist:
        min_dist = max_dist
        min_idx = max_idx
print(*conv[min_idx])