题目描述

Farmer John's $N$ cows $(1≤N≤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 ith cow is located at a distinct location $(x_i,y_i)$ where $0≤x_i≤10^6$ and $0≤y_i≤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.

输入格式

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

题目大意

题目描述

农夫约翰有N头牛（1<=N<=1e5） 它们在农场里分布的极其的远，因此希望你建立一个通讯网络，便于它们更容易地交换电子短信（当然，这些短信都包含“moo（哞）”的变形体，即数字）

第i头牛位于位置(xi，yi）其中0<=x<=1e6, 0<=y<=10. 在牛i与牛j之间建立通信链路的成本是它们之间的距离，即（xi-xj）2+（yi-yj）2。

请聪明的你构建一个所有奶牛都能交流的最低成本的通信网络。如果两头奶牛通过一条链接直接连接或者它们的信息可以沿着一条链接传播，那么认为他们可以通信。

注意 此问题时间限制为4秒

输入格式

第一行输入为N，接下来N行分别描述奶牛的位置（x，y） 均为整数

输出格式

请输出允许所有奶牛通信的网络的最低成本。请注意，此开销可能太大，无法放入32位整数中，并且可能需要使用64位整数（例如，C++中的“long long”）

说明/提示

测试点2~3满足N<=1000 测试点4~15没有特殊限制

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

660

提示

【数据范围】

• Test cases 2-3 satisfy $N≤1000$.
• Test cases 4-15 satisfy no additional constraints.