【问题描述】

在二维平面上有 N 个不同整数坐标的点（xi,yi），任意两点 I 和 j 直接相连的代价为

（(xi−xj)2+(yi−yj)2）。求把所有点连通起来的最小代价。

【输入格式】

第一行为 n，接下来 n 行，每行两个整数（xi,yi），如题意。

【输出格式】

最小代价。

【输入样例】

10

83 10

77 2

93 4

86 6

49 1

62 7

90 3

63 4

40 10

72 0

【输出样例】

660

【数据范围】

对于 20%的数据，N<=1000。

对于 100%的数据，N<=1e5，0<=xi<=1e6,0<=yi<=10。

代码奉上，为什么样例输出663啊！

---

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node1
{int x,y;}a[100010];
struct node
{int u,nxt,w;}e[200010];
int n,tot;
int f[100010];
map<int,bool>mp[100010];
int ans,yl;
int getf(int x)
{
	if(f[x]==x) return x;
	else return f[x]=getf(f[x]);
}
void add(int u,int v)
{
	int w=abs(a[u].x-a[v].x)*abs(a[u].x-a[v].x)+abs(a[u].y-a[v].y)*abs(a[u].y-a[v].y);
	e[++tot].u=u;
	e[tot].w=w;
	e[tot].nxt=v;
}
int read()
{
	char c=getchar();int x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x; 
}
bool cmp(node1 x,node1 y)
{return x.x<y.x;}
bool cmp1(node1 x,node1 y)
{return x.y<y.y;}
bool cmp2(node x,node y)
{return x.w<y.w;}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) f[i]=i,a[i].x=read(),a[i].y=read();
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<n;i++)
		add(i,i+1),add(i+1,i),mp[i][i+1]=1;
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<n;i++)
		if(mp[i][i+1]) continue;
		else add(i,i+1),add(i+1,i);
	sort(e+1,e+1+tot,cmp2);
	for(int i=1;i<=tot;i++)
	{
		if(yl==n-1) break;
		int u=getf(e[i].u),v=getf(e[i].nxt);
		if(u==v) continue;
		f[u]=v;
		ans+=e[i].w;
		yl++;
	}
	cout<<ans;
	return 0;
}