记录编号	248510	评测结果	WWWWWWWW
题目名称	[Ural 1143] 青蛙的烦恼	最终得分	0
用户昵称	安呐一条小咸鱼。	是否通过	未通过
代码语言	C++	运行时间	0.017 s
提交时间	2016-04-10 16:13:15	内存使用	0.75 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double x[80],y[80],f[80][80];
double father[20001];
double dist(int i,int j)
{
	return sqrt( abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]) );
}
struct pri
{
	double a,b,road;
}_node[10001];
bool cmp(pri a,pri b)
{
	return a.road<b.road;
}
double find(int x)
{
	if(father[x]!=x)father[x]=find(father[x]);
	return father[x];
}
void unionn(int r1,int r2)
{
	father[r2]=r1;
}
int main()
{
	freopen("frogpuzzle.in","r",stdin);
	freopen("frogpuzzle.out","w",stdout);
	int n;
	double ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
	}
	for(int i=1;i<4001;i++)
   {
   	 	father[i]=i;
   }
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i<j)
			{
				_node[i].a=i;
				_node[i].b=j;
				_node[i].road=dist(i,j); 
			}
		} 
	}
	 for(int i=1;i<=n;i++)
   {
		int r1=find(_node[i].a);
		int r2=find(_node[i].b);
		if(r1==r2)
		{
			printf("%.3lf\n",_node[i].road);
			return 0;
		}
		unionn(find(_node[i].b+n),r1);
		unionn(find(_node[i].a+n),r2);
   }
}