Time Limit: 1000MS   Memory Limit: 65536KB   64bit IO Format: %lld & %llu

Description

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. 
Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

Input

The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

Output

Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

Sample Input

3
1.0 1.0
2.0 2.0
2.0 4.0

Sample Output

3.41

Source

 
最小生成树。注意double
 
 /*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int mxn=;
int n;
struct point{
double x;double y;
}p[mxn];
double dist(point a,point b){
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
struct edge{
int x,y;
double dis;
}e[mxn*mxn];int cnt=;
int cmp(edge a,edge b){
return a.dis<b.dis;
}
int fa[mxn];
void init(){
for(int i=;i<=n;i++)fa[i]=i;
}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
double ans=;
void Kruskal(){
int i,j;
int ti=;
ans=;
for(i=;i<=cnt;i++){
int u=find(e[i].x),v=find(e[i].y);
if(u==v)continue;
ti++;
ans+=e[i].dis;
fa[u]=v;
if(ti==n-)break;
}
return;
}
int main(){
int i,j;
while(scanf("%d",&n)!=EOF){
init();
cnt=;
int u,v,dis;int m;
int i,j;
for(i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i=;i<n;i++)
for(j=i+;j<=n;j++){
e[++cnt]=(edge){i,j,dist(p[i],p[j])};
}
sort(e+,e+cnt+,cmp);
Kruskal();
printf("%.2f\n",ans);
}
return ;
}

最新文章

  1. HTTP协议学习--- (十一)理解HTTP幂等性
  2. js中有趣的闭包(closure)
  3. [转]C++ string的trim, split方法
  4. Bootstrap——Jumbotron编写
  5. 使用Code First 创建数据库
  6. MarkDown写作技巧
  7. objective-c对NSArray的学习
  8. Lua Script
  9. cocos 事件分发2
  10. Sharepoint 问题集锦 - 外部列表(external list) - 读取当前用户上下文或用户名作为筛选参数
  11. 高效搭建Spark全然分布式集群
  12. WM_SYSCOMMAND包括很多功能,比如:拖动左边框、拖动标题栏、滚动条滚动、点击最小化、双击标题栏——Delphi 通过事件代替了大部分常用的消息,所以Delphi 简单、易用、高效
  13. apache-maven-3.2.1设备
  14. 如何在在网页上显示pdf文档
  15. Spring Boot消息队列应用实践
  16. 谈谈Ext JS的组件——组件基类:Ext.Component
  17. Django 应用程序 + 模型 + 基本数据访问
  18. UEditor学习笔记1
  19. PMP证书的获取,不知道10大注意事项会吃亏
  20. MySQL学习笔记(三)数据优化

热门文章

  1. shiro : java.lang.IllegalArgumentException: Odd number of characters.
  2. 使用JDK自带的工具jstack找出造成运行程序死锁的原因
  3. App Store上的开源应用汇总
  4. KissXML的XPath选取问题
  5. mysql安装(docker)
  6. [Android 测试] 压力稳定性测试之: Monkey 详解分析脚本(转载)
  7. C#导入有道词典单词本到扇贝
  8. quartz测试类
  9. Qt读写excel
  10. C++系统学习之六:函数