음머캐스트

농부 존의 소 \(N\)마리(\(1 \leq N \leq 1000\))는 중요한 소식을 서로에게 방송하기 위한 비상 "음머캐스트(moo-cast)" 시스템을 조직하려고 한다.

먼 거리에서 서로 음머 하고 울부짖는 대신, 소들은 한 마리당 하나씩 무전기를 갖추기로 했다. 각 무전기는 전송 반경에 제한이 있지만, 소들은 여러 번의 중계를 거치는 경로를 따라 메시지를 전달할 수 있으므로 모든 소가 다른 모든 소에게 직접 전송할 수 있을 필요는 없다.

소들은 무전기에 얼마를 쓸지 결정해야 한다. \$X를 쓰면 각자 거리 \(\sqrt{X}\)까지 전송할 수 있는 무전기를 하나씩 갖게 된다. 즉, 두 소가 통신할 수 있으려면 두 소 사이 거리의 제곱이 \(X\) 이하여야 한다.

어느 소에서 시작한 방송이든 결국 다른 모든 소에게 도달할 수 있도록 하는 최소의 정수 \(X\) 값을 구해 소들을 도와주자.

문제 출제: 리처드 펭(Richard Peng)

문제 출제: 리처드 펭(Richard Peng)

입력의 첫째 줄에 \(N\)이 주어진다.

다음 \(N\)개의 줄에는 각 소의 \(x\), \(y\) 좌표가 주어진다. 두 값 모두 \(0 \ldots 25,000\) 범위의 정수이다.

소들이 무전기에 써야 하는 최소 금액을 나타내는 정수 \(X\)를 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Gold