Minimum Communication Network Cost

Farmer John's N cows (1 \leq N \leq 10^5) are located at distinct positions \((x_i,y_i)\) with \(0 \leq x_i \leq 10^6\) and \(0 \leq y_i \leq 10\). In order for the cows to exchange electronic text messages (each containing some variant of "moo"), a communication network must be built. The cost to build a direct communication link between cow \(i\) and cow \(j\) is given by the squared Euclidean distance:

[ \text{cost}(i,j)= (x_i - x_j)^2 + (y_i - y_j)^2, ]

The goal is to compute the minimum total cost required to build a network that connects all the cows, either via direct links or via sequences of links. In other words, you must find the cost of a minimum spanning tree (MST) over the complete graph where each node represents a cow and the weight of the edge between any two cows is the squared distance between them.

Note: The time limit for this problem is 4 seconds.

inputFormat

The first line contains an integer N, the number of cows. The next N lines each contain two integers x and y, representing the coordinates of a cow. It is guaranteed that all cows have distinct positions and that \(0 \leq x \leq 10^6\) and \(0 \leq y \leq 10\).

outputFormat

Output a single integer, the minimum total cost to connect all the cows in a communication network.

sample

2
0 0
1 0

1