Advertisement
Guest User

Untitled

a guest
Jun 23rd, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. #define sqr(a) ((a)*(a))
  5. using namespace std;
  6.  
  7. #pragma pack(1)
  8.  
  9. int i, j, k, o, x, y, n, m, pr[5000+10], sz[5000+10];
  10. long double ans;
  11. struct my
  12. {
  13. int x;
  14. int y;
  15. int d;
  16. };
  17. my b[1000000*15];
  18. pair<int, int> a[5000+10];
  19. inline int dist(int x, int y, int xx, int yy)
  20. {
  21. int k=(sqr(x-xx)+sqr(y-yy));
  22. return k;
  23. }
  24. bool cmp(my a, my b)
  25. {
  26. if (a.d<b.d) return true;
  27. return false;
  28. }
  29. int get(int v)
  30. {
  31. if (v==pr[v]) return v;
  32. int res = get(pr[v]);
  33. pr[v] = res;
  34. return res;
  35. }
  36.  
  37. int main()
  38. {
  39. ios_base::sync_with_stdio(0);
  40. cin.tie(0);
  41. cout.tie(0);
  42. cin>>n;
  43. for (i=1;i<=n;i++)
  44. {
  45. cin>>a[i].f>>a[i].s;
  46. pr[i]=i;
  47. sz[i]=0;
  48. }
  49. for (i=1;i<n;i++)
  50. {
  51. for (j=i+1;j<=n;j++)
  52. {
  53. int len=dist(a[i].f, a[i].s, a[j].f, a[j].s);
  54. m++;
  55. b[m].x=i;
  56. b[m].y=j;
  57. b[m].d=len;
  58. }
  59. }
  60. sort(b+1, b+m+1, cmp);
  61.  
  62. for (i=1;i<=m;i++)
  63. {
  64.  
  65. x=get(b[i].x);
  66. y=get(b[i].y);
  67.  
  68. if (x!=y)
  69. {
  70.  
  71. ans+=sqrt(sqr(a[b[i].x].f-a[b[i].y].f)+sqr(a[b[i].x].s-a[b[i].y].s));
  72. if (rand()&1) swap (x, y);
  73. pr[x]=y;
  74. }
  75.  
  76.  
  77. }
  78. cout.precision(12);
  79. cout<<fixed;
  80. cout<<ans;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement