음머 네트워크

농부 존의 \(N\)마리 소(\(1 \leq N \leq 10^5\))는 농장 곳곳에 멀리 흩어져 있으며, 전자 문자 메시지(당연히 모두 "음머"의 변형을 담고 있다)를 더 쉽게 주고받을 수 있도록 통신 네트워크를 구축하고 싶어 한다.

\(i\)번째 소는 서로 다른 위치 \((x_i,y_i)\)에 있으며, \(0 \leq x_i \leq 10^6\)이고 \(0 \leq y_i \leq 10\)이다. 소 \(i\)와 \(j\) 사이에 통신 링크를 구축하는 비용은 두 소 사이 거리의 제곱, 즉 \((x_i-x_j)^2 + (y_i-y_j)^2\)이다.

모든 소가 서로 통신할 수 있는 통신 네트워크를 구축하는 데 필요한 최소 비용을 계산하여라. 두 소는 링크로 직접 연결되어 있거나, 메시지가 전달될 수 있는 링크의 연속이 존재하면 통신할 수 있다.

*참고: 이 문제의 시간 제한은 4초로, 기본값의 두 배이다.*

Problem credits: Brian Dean

채점 방식

• 테스트 케이스 2-3은 \(N \le 1000\)을 만족한다.
• 테스트 케이스 4-15는 추가 제약이 없다.

Problem credits: Brian Dean

첫째 줄에 \(N\)이 주어지고, 다음 \(N\)개의 줄에는 각 소의 \(x\), \(y\) 좌표가 주어진다. 모두 정수이다.

모든 소가 통신할 수 있는 네트워크의 최소 비용을 출력한다. 이 비용은 32비트 정수에 담기에는 너무 클 수 있으므로 64비트 정수(예: C++의 "long long" 정수)를 사용해야 할 수 있음에 유의한다.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > February > Gold