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.

*Note: the time limit for this problem is 4s, twice the default.*

Problem credits: Brian Dean

SCORING

• Test cases 2-3 satisfy \(N \le 1000\).
• Test cases 4-15 satisfy no additional constraints.

Problem credits: Brian Dean

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++).

riseoj 작성

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