문제
N마리의 오리들이 원활한 커뮤니케이션을 위하여 메시지 전송 시스템을 구축하려고 한다.
그래서 오리들은 긴 거리에도 불구하고 서로에게 꽥꽥거리는 대신 각자 무전기를 하나씩 장착하기로 결정했다.
이 무전기들은 제한된 반경에서만 소통이 가능하기에 여러 오리를 거쳐 전달하는 방식을 취하기로 했다.
무전기의 통신 가능한 범위는 무전기의 가격에 따라 달라진다.
만약 X원에 무전기들을 구입한다면 모든 무전기의 통신 범위는 √X로 정해진다.
두 오리 사이의 통신이 가능하려면 두 오리 사이의 유클리드 거리가 √X 이하여야한다.
오리들이 모두 통신을 하기 위해 필요한 무전기를 구입하기 위한 최소 무전기 비용을 알아내자.
입력
첫 번째 줄에는 오리의 수 N이 주어진다. (1≤N≤1000)
두 번째 줄부터 N줄에 걸쳐 각 오리들의 x, y 좌표 위치가 주어진다. 모든 위치는 0에서 25,000 사이의 정수로 이루어진다.
출력
필요한 최소 무전기 가격을 출력하시오.
예제
4
1 3
5 4
7 2
6 1
17
태그
출처
USACO 2016 December Gold
로그인해야 코드를 작성할 수 있어요.