这题对于Kruskal算法OIer极度不友好，在这里提供一个有趣的卡常优化想法。（不想看分析的直接看【写法】）

【分析】

当 $n$ $=$ $5000$ 时，Kruskal 算法需要处理 $1.25$ $\times$ $10^8$ 条边，这样庞大的边数 Kruskal 算法肯定吃不消。我们需要牺牲一点正确性来换取时空复杂度。考虑到你实际上只需要 $n$ $-$ $1$ $=$ $5000$ $-$ $1$ $=$ $4999$ 条边，此时一定需要删除一些无用的边。两个点之间的间距的平均值约是 $\sqrt{2}$ $\times$ $2000000\div5000$ $=$ $570$ 这个值，我们可以把这个值扩大一些倍数，我选择扩大不到 $400$ 倍，取一个比较整的数 $2$ $\times$ $10^5$， 为了防止 $n$ 比较小时漏解，当 $n$ $\le$ $1000$ 时我们正常计算，就可以了。

【写法】

所以我们只对 $dis(i,j)$ $\le$ $1$ $\times$ $10^6$ 时的边或 $n$ $\le$ $1000$ 时的所有边建边即可

【实现】 我贴出我的代码片段

if(sqrt((x[i]-x[j])*(x[i]-x[j])
  +(y[i]-y[j])*(y[i]-y[j]))<=1000000.0){
	graph[m]=(Edge){i,j,sqrt((x[i]-x[j])*(x[i]-x[j])
	  +(y[i]-y[j])*(y[i]-y[j]))};
	m++;				
}

【提示】

友情提醒，这并不是一篇正经的题解，所以大佬们也就不用费心去 hack 了，还有就是这应该不是正解，别喷，希望写正解的酌情略过。

作者的记录：https://www.luogu.com.cn/record/84675206