BOJ 25782 Desert Travel

문제 링크:

문제 내용

좌표평면에 $n$개의 점이 있습니다. $a$번 점에서 $b$번 점으로 이동하려고 할 때, 그 과정에서 0개 이상의 점을 거쳐서 갈 수 있습니다. 한 점에서 다른 점으로 직접 이동할 때는 그 거리만큼의 비용이 들며, 경로 전체의 비용은 각각의 비용의 최댓값입니다. $(a, b)$의 쌍이 여러 개 주어질 때, 각각에 대해 최소 비용을 구하세요.

입력

첫 줄에는 점의 개수 $n$이 주어집니다. ($1 \le n \le 5000$)

다음 $n$줄에는 각 점의 좌표 $(x, y)$가 한 줄에 하나씩 주어집니다. ($-10^6 \le x_i, y_i \le 10^6$) 좌표는 모두 정수입니다.

다음 줄에는 쿼리의 개수 $q$가 주어집니다. ($1 \le q \le 500\;000$)

다음 $q$줄에는 각 쿼리의 정보 $(a, b)$가 한 줄에 하나씩 주어집니다. ($1 \le a, b \le n$)

출력

각 쿼리에 대해, $a$에서 $b$로 가는 경로 중 비용이 가장 작은 것의 비용을 출력하세요. 절대 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다.

문제 풀이