[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 17371번 _ 이사

https://www.acmicpc.net/problem/17371

17371번: 이사

[문제]

[입력]

첫 번째 줄에 편의시설의 개수 N(1 ≤ N ≤ 10**3)이 주어진다.

다음 N개의 줄의 각 줄에는 두 정수 x와 y(-10**4 ≤ x, y ≤ 10**4)가 공백 하나를 사이에 두고 주어진다. 이는 (x, y)에 편의시설이 하나 존재한다는 뜻이다.

[출력]

첫 번째 줄에 혜아가 이사할 곳의 좌표 (Hx, Hy)를 나타내는 두 실수 Hx, Hy를 공백 하나로 구분하여 출력한다. 가장 가까운 편의시설까지의 거리와 가장 먼 편의시설까지의 거리의 평균을 정답과 비교했을 때 절대오차 혹은 상대오차가 10-6 이하면 정답으로 인정한다.

 

[아이디어]

1) 집의 위치가 될 수 있는 점의 좌표는 무수히 많다. 스페셜 저지인 이유도 그래서다.

2) 정답이 될 수 있는 좌표들의 집합은 특정 두 편의시설을 이은 선분의 일부일 수밖에 없다. (가장 가까운 편의 시설과 가장 먼 편의 시설까지의 거리 합의 최소는 직선으로 이었을 때이기 때문)

3) 예를 들어, 예시 입력의 정답은 두 점 (0,1)과 (4, -3)을 이은 선분 중 가장 가까운 점이 (0,1)이고 가장 먼 점이 (4, -3)이라는 조건이 깨지기 전까지이므로, (0,1)부터 (2/3, 1/3)의 선분 위의 모든 점이 정답에 해당한다. (그보다 오른쪽으로 움직이면, 가장 먼 점이 (-4,1)로 바뀐다.)

4) 3)의 사실로부터, 편의 시설의 위치 중 하나가 무조건 답이 될 수 있음을 알 수 있다.

5) 다른 모든 편의 시설까지의 거리 중 최댓값이 가장 작은 점이 정답 중 하나가 된다.

 

n=int(input())
d=[tuple(map(int,input().split())) for _ in range(n)]
def f(i,j):
    return (d[i][0]-d[j][0])**2+(d[i][1]-d[j][1])**2
m=int(1e9)
for i in range(n):
    t=0
    for j in range(n):
        t=max(t,f(i,j))
    if m>t:
        m=t;a=i
print(*d[a])

처음에 편의 시설의 위치는 답이 되면 안된다고 생각해서 시간 낭비가 있었다.