#PU1211. USACO 2022 February Contest, Gold — Problem 3. Moo Network

    ID: 1336 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb22来源:usaco.orgscoring:equal_test_cases最小生成树

USACO 2022 February Contest, Gold — Problem 3. Moo Network

USACO 2022 February Contest, Gold — Problem 3. Moo Network

题目描述

Farmer John's NN cows (1≤N≤1051 \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 iith cow is located at a distinct location (xi,yi)(x_i,y_i) where 0≤xi≤1060 \leq x_i \leq 10^6 and 0≤yi≤100 \leq y_i \leq 10. The cost of building a communication link between cows ii and jj is the squared distance between them: (xi−xj)2+(yi−yj)2(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 NN, and the next NN lines each describe the xx and yy 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 N≤1000N \le 1000. 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