시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 406 | 133 | 98 | 35.897% |
Farmer John's $N$ cows ($1 \leq N \leq 10^5$) are spread far apart on his farm and would like to build a communication network so they can more easily exchange electronic text messages (all of which of course contain variations of "moo").
The $i$th cow is located at a distinct location $(x_i,y_i)$ where $0 \leq x_i \leq 10^6$ and $0 \leq y_i \leq 10$. The cost of building a communication link between cows $i$ and $j$ is the squared distance between them: $(x_i-x_j)^2 + (y_i-y_j)^2$.
Please calculate the minimum cost required to build a communication network across which all the cows can communicate. Two cows can communicate if they are directly connected by a link, or if there is a sequence of links along which their message can travel.
The first line of input contains $N$, and the next $N$ lines each describe the $x$ and $y$ coordinates of a cow, all integers.
Please output the minimum cost of a network that will allow all cows to communicate. Note that this cost might be too large to fit into a 32-bit integer and may require use of 64-bit integers (e.g., "long long" integers in C++).
10 83 10 77 2 93 4 86 6 49 1 62 7 90 3 63 4 40 10 72 0
660