Advertisement
Guest User

Untitled

a guest
Feb 19th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. var
  2. i,n,z,m,k,j:longint;
  3. cost:double;
  4. x,y,a,p,b,rank:array[1..25000000]of longint;
  5. w:array[1..25000000]of double;
  6. procedure sort(l,r:longint);
  7. var i,j,k:longint;
  8. e,t:longint;
  9. begin
  10. i:=l;
  11. j:=r;
  12. e:=w[l+random(r-l+1)];
  13. while i<=j do
  14. begin
  15. while e>w[i] do inc(i);
  16. while e<w[j] do dec(j);
  17. if i<=j then
  18. begin
  19. t:=w[i];w[i]:=w[j];w[j]:=t;
  20. k:=a[i];a[i]:=a[j];a[j]:=k;
  21. k:=b[i];b[i]:=b[j];b[j]:=k;
  22. inc(i);
  23. dec(j);
  24. end;
  25. end;
  26. if i<r then sort(i,r);
  27. if j>l then sort(l,j);
  28. end;
  29. function find(x:longint):longint;
  30. begin
  31. if x<>p[x] then p[x]:=find(p[x]);
  32. find:=p[x];
  33. end;
  34. procedure union(x,y:longint);
  35. begin
  36. x:=find(x);
  37. y:=find(y);
  38. if rank[x]>rank[y] then p[y]:=x else p[x]:=y;
  39. if rank[x]=rank[y] then inc(rank[y]);
  40. end;
  41. begin
  42. assign(input,'unionday.in');reset(input);
  43. assign(output,'unionday.out');rewrite(output);
  44. read(n);
  45. for i:=1 to n do
  46. read(x[i],y[i]);
  47.  
  48. m:=0;
  49. for i:=1 to n do
  50. for j:=i+1 to n do
  51. begin
  52. inc(m);
  53. a[m]:=i;
  54. b[m]:=j;
  55. w[m]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
  56. end;
  57.  
  58. sort(1,m);
  59. for i:=1 to n do
  60. begin
  61. p[i]:=i;
  62. rank[i]:=0;
  63. end;
  64.  
  65. z:=0;
  66. cost:=0;
  67. for i:=1 to m do
  68. begin
  69. if find(a[i])<>find(b[i]) then
  70. begin
  71. union(a[i],b[i]);
  72. cost:=cost+w[i];
  73. end;
  74. end;
  75.  
  76. writeln(cost:0:5);
  77. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement