Guest User

Untitled

a guest
Jan 19th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. double dist(int x1,int y1,int x2,int y2)
  9. {
  10. return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
  11. }
  12. int main()
  13. {
  14. int n,i,j;
  15. int x[101],y[101];
  16. bool vis[101];
  17. double res=0.0,najmalo_dist;
  18. int cnt,teme;
  19. memset(vis,false,sizeof(vis));
  20.  
  21. cin>>n;
  22.  
  23.  
  24. for(i=1;i<=n;i++)
  25. {
  26. cin>>x[i]>>y[i];
  27. }
  28.  
  29. cnt=1;
  30. vis[1]=true;
  31.  
  32. double t;
  33. while(cnt<n)
  34. {
  35. najmalo_dist=1000000.0; //very big double
  36. teme=-1;
  37. for(i=1;i<=n;i++) //za poseteni
  38. {
  39. if(vis[i]==false) continue;
  40.  
  41. for(j=1;j<=n;j++) //za neposeteni
  42. {
  43. if(vis[j]==true) continue;
  44. t=dist(x[i],y[i],x[j],y[j]);
  45.  
  46. if(t<najmalo_dist)
  47. {
  48. najmalo_dist=t;
  49. teme=j;
  50. }
  51.  
  52. }
  53. }
  54.  
  55. res+=najmalo_dist;
  56. vis[teme]=true;
  57. cnt++;
  58. }//end_while
  59.  
  60. int r=res*100;
  61. cout<<r/100<<"."<<(r/10)%10<<r%10<<endl;
  62. return 0;
  63. }
Add Comment
Please, Sign In to add comment