USACO

USACO 2022 February Contest, Gold

Problem 3. Moo Network

Contest has ended.

Log in to allow submissions in analysis mode

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.**

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains

$N$ , and the next

$N$ lines each describe the

$x$ and

$y$ coordinates of a cow, all integers.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

SAMPLE OUTPUT:

SCORING:

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

Problem credits: Brian Dean

Contest has ended. No further submissions allowed.