#PU1211. USACO 2022 February Contest, Gold — Problem 3. Moo Network
USACO 2022 February Contest, Gold — Problem 3. Moo Network
USACO 2022 February Contest, Gold — Problem 3. Moo Network
题目描述
Farmer John's cows () 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 th cow is located at a distinct location where and . The cost of building a communication link between cows and is the squared distance between them: . 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 , and the next lines each describe the and 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++).
数据范围
Test cases 2-3 satisfy . Test cases 4-15 satisfy no additional constraints. Problem credits: Brian Dean
样例
样例 1
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
660