Advertisement
Guest User

Untitled

a guest
Mar 10th, 2015
294
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include<iostream>
  2. #include<cmath>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<cstdio>
  6. using namespace std;
  7. int x[5001],y[5001];
  8. const double INF=100000000;
  9. double dest(int x1,int y1,int x2,int y2)
  10. {
  11. return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
  12. }
  13. bool used[5001];
  14. double d[5001];
  15. int main()
  16. {
  17. freopen("unionday.in","r",stdin);
  18. freopen("unionday.out","w",stdout);
  19. int n;
  20. cin>>n;
  21. for(int i=0;i<n;i++)
  22. {
  23. cin>>x[i]>>y[i];
  24. }
  25. for(int i=0;i<n;i++) d[i]=INF;
  26. d[0]=0;
  27. double ans=0;
  28. for(int i=0;i<n;i++)
  29. {
  30. double best=INF;
  31. int cur=0;
  32. for(int j=0;j<n;j++)
  33. {
  34. if(d[j]<best && !used[j])
  35. {
  36. cur=j;
  37. best=d[j];
  38. }
  39. }
  40. used[cur]=true;
  41. ans+=best;
  42. for(int j=0;j<n;j++)
  43. {
  44. d[j]=min(d[j],dest(x[cur],y[cur],x[j],y[j]));
  45. }
  46. }
  47. cout.precision(8);
  48. cout<<fixed<<ans<<endl;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement