p114 Freckles 和上一题一样，还是最小生成树，只不过输入的是double坐标

#include <stdio.h>//还是用double的时候一定注意是不是用%d或者%f输入了，都不对，应该是%lf
#include <algorithm>//注意是不是吧=把double赋值给一个int之后再输出了
#include <math.h>

#define N 101
using namespace std;

int Tree[N];

struct edge{
	int a,b;
	double cost;
	bool operator < (const edge& A) const{
		return cost<A.cost;
	}
}ee[6000];

struct point{
	double x,y;
	double dis(point P)
	{
		return sqrt((P.x-x)*(P.x-x)+(P.y-y)*(P.y-y));
	}
}pp[N];

int root(int x)
{
	if(Tree[x]==-1)return x;
	else
	{
		int tmp = root(Tree[x]);
		Tree[x] = tmp;
		return tmp;
	}
}




int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)Tree[i]=-1;
		
		for(int i=1;i<=n;i++)
		{
			scanf("%lf %lf",&pp[i].x,&pp[i].y);//又是%d与%f分不清 //double必须写成%lf！！ 
		}
		
		int ind = 1;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				ee[ind].a=i;
				ee[ind].b=j;
				ee[ind].cost=pp[i].dis(pp[j]);
				ind++;
			}		
		}
		sort(ee+1,ee+1+n*(n-1)/2);
		double ans=0.0;
		for(int i=1;i<=n*(n-1)/2;i++)
		{
			int x = root(ee[i].a);
			int y = root(ee[i].b);
			if(x!=y)
			{
				Tree[x]=y;
				ans+=ee[i].cost;
			}
			
		}
		
		//别忘了格式化输出 
		printf("%.2f\n",ans);	
	 } 
	return 0;
 } #include <stdio.h>//还是用double的时候一定注意是不是用%d或者%f输