문제
농부 창호의 N마리 소들이 멀리 퍼져있어서 소들이 서로 의사소통을 하기 위해 음메 네트워크를 구축하려고 한다.
i번째 소는 (xi , yi)에 존재하며 i번째 소와 j번째 소 사이의 연결 비용은 (xi- xj)<2 + (yi- yj)2 이다.
어느 소가 다른 모든 소와 통신 가능한 음메 네트워크를 구축하는데 필요한 최소 비용을 구하라.
입력
첫 번째 줄에 소의 수 N이 주어진다. ( 1 ≤ N ≤ 105 )
N줄에 걸쳐 i번째 소의 위치 xi, yj가 주어진다. ( 0 ≤ xi≤ 106, 0 ≤ yi ≤ 10 )
출력
음메 네트워크를 구축하는 최소 비용을 출력하시오.
(C++의 경우 long long이 필요할 수 있습니다.)
예제1
입력
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
출력
660
출처
USACO 2022 February Gold