P8191 [USACO22FEB] Moo Network G

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

N/A

N/A

【数据范围】 - Test cases 2-3 satisfy $N≤1000$. - Test cases 4-15 satisfy no additional constraints.