#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int father[1001]; //1-1000 最大范围!编号是从1开始的舍弃1
void InitDisjoint(int n) //初始化集合
{
for(int i = 0 ; i < n ;i++)
{
father[i] = i ; //初始时每个结点各自为一个集合,父结点指向自己即自己就是根!
}
}
int FindDisjointSet(int u) //压缩路径查找
{
if(u==father[u])//查找到当前结点的根! //递归结束条件
{
return u; //返回当前集合的根结点
}else
{
father[u] = FindDisjointSet(father[u]); //将当前结点的父结点直接指向当前集合的根!
return father[u]; //返回u结点的父节点(根)
}
}
void UnionDisjointSet(int u, int v) //将结点v合并到结点u 顶点
{
int uroot = FindDisjointSet(u); //寻找u的根(最上面的祖先结点)
int vroot = FindDisjointSet(v);//寻找v的根(最上面的祖先结点)
father[vroot] = uroot; //v的父亲结点指向u结点 可以自己指向自己!3-3输入也合法!
}
typedef struct Vertex //顶点信息用坐标表示
{
float x;
float y;
Vertex(float x1 , float y1)//构造函数
{
x = x1;
y = y1;
}
};
typedef struct Edge
{
int begin; //起始位置
int end; //终止位置
float weight;//距离
Edge(int begin1 , int end1 , float weight1) //构造函数
{
begin = begin1;
end = end1;
weight = weight1;
}
};
float getdis(Vertex x,Vertex y){ //计算2点之间的距离根号下(x1-x2)*(x1-x2)+...
return pow((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y),0.5);
}
bool compare (Edge lhs , Edge rhs)
{
return lhs.weight < rhs.weight; //按权值排序,左小右大
}
int main()
{
//获得两个点以及两个点间的距离,然后从集合中找出距离的最小值。加入到图的集合中,当把所有边都遍历
//完后,由于这个题,图肯定是连通的。所以只要记录加进来的边的长度(也就是两点间的距离就行)
int n ;
scanf("%d",&n);
InitDisjoint( n + 1); //初始化并查集
float total = 0;
vector<Vertex> vertex; //保存顶点信息
vector<Edge> edge; //保存边结点
for(int i = 0 ; i < n ; i++)
{
float x,y;
scanf("%f%f",&x,&y);
Vertex v(x,y);
vertex.push_back(v); //把点保存起来
}
//计算任意两个顶点直接的距离作为权值 (i,j) 以下标作为顶点的起始和终止1-2...n-n+1
for( int i = 0 ; i < vertex.size() -1 ; i++) { //-1 j才不会数组超过范围
for (int j = i+1; j < vertex.size(); j++) {
//i-j的距离作为权值
float weight = getdis(vertex[i],vertex[j]);
Edge e( i, j , weight); //存入边结点
//将边信息保存
edge.push_back(e);
}
}
//按权值(距离)将边信息从小到达排序
sort(edge.begin(),edge.end(),compare);
int CountEdgeNum = 0;
for(int i = 0 ; i < edge.size() ;i++) //遍历整个边表数组
{
//取出每一组边结点信息 执行基于并查集的最小生成树算法
int u = edge[i].begin;
int v = edge[i].end;
float weight = edge[i].weight;
if(FindDisjointSet(u) != FindDisjointSet(v))
{
UnionDisjointSet(u,v);
CountEdgeNum++; //边数+1
total += weight; //权值累加
if( CountEdgeNum == n-1) //提前结束(符合树的定义)边数==顶点数-1
{
break;
}
}
}
printf("%.2f\n",total);
return 0;
}