本文共 2364 字，大约阅读时间需要 7 分钟。

Eddy's picture

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 7   Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Eddy begins to like  painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room,  and he usually  puts out his newest pictures to let his friends appreciate. but the result it can be imagined, the friends are not interested in his picture.Eddy feels very puzzled,in order to change all friends 's view to his technical of painting  pictures ,so Eddy creates a problem for the his friends of you.

Problem descriptions as follows: Given you some coordinates pionts on a drawing paper, every point links with the ink with the straight line, causes all points finally  to link in the same place. How many distants does your duty discover the shortest length which the ink draws?

Input

The first line contains 0 < n <= 100, the number of point. For each point, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the point.

Input contains multiple test cases. Process to the end of file.

Output

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

Sample Input

31.0 1.02.0 2.02.0 4.0

Sample Output

3.41

Author

eddy

 

 

唔 这道题呢是一道很简单的最小生成树问题 大意就是给你n个点的坐标，让你使得这些点都能够连在一起而且路径最短，显然这道题可以用Prim算法的模板进行套用，但是唯一需要注意的一个地方就是，因为这道题给你的是n个点的坐标，而你需要将各个坐标一一转化为这n个点的边长再进行Prim算法的操作，所以在这之前还得再加上一个函数，专门用来计算两点间的距离，当然n个点坐标的存储用结构体会方便许多，那么这些前期工作做好了 再按照题意进行输入输出就可以了。。。当然今天交的时候不小心在初始化vis数组的时候写成了memset(vis,0,sizeof(0))然而样例只有一组所以不影响结果我也没有去管 看了样例过了就交了两次结果连着WA了，下次这种低级错误还是尽可能的避免才好= = 代码如下

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;double d[10005];double map[10005][10005];int vis[10005];int n;const double MAX=1000000.0;struct  Point {    double x;    double y; }point[10005];double  dis(int i,int j){ return (double)sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));}double   Prim(int n){    int i,j,id;    double mins,ans=0;    for(i=0;i
        
         d[i]) { mins=d[i]; id=i; } } if(mins==MAX) return -1; vis[id]=1; ans+=mins; for(i=0;i
         
          >point[i].x>>point[i].y; } for(i=0;i
         
        
       
      
     
    
   

 

转载地址：http://fupws.baihongyu.com/