Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- var
- i,n,z,m,k,j:longint;
- cost:double;
- x,y,a,p,b,rank:array[1..25000000]of longint;
- w:array[1..25000000]of double;
- procedure sort(l,r:longint);
- var i,j,k:longint;
- e,t:longint;
- begin
- i:=l;
- j:=r;
- e:=w[l+random(r-l+1)];
- while i<=j do
- begin
- while e>w[i] do inc(i);
- while e<w[j] do dec(j);
- if i<=j then
- begin
- t:=w[i];w[i]:=w[j];w[j]:=t;
- k:=a[i];a[i]:=a[j];a[j]:=k;
- k:=b[i];b[i]:=b[j];b[j]:=k;
- inc(i);
- dec(j);
- end;
- end;
- if i<r then sort(i,r);
- if j>l then sort(l,j);
- end;
- function find(x:longint):longint;
- begin
- if x<>p[x] then p[x]:=find(p[x]);
- find:=p[x];
- end;
- procedure union(x,y:longint);
- begin
- x:=find(x);
- y:=find(y);
- if rank[x]>rank[y] then p[y]:=x else p[x]:=y;
- if rank[x]=rank[y] then inc(rank[y]);
- end;
- begin
- assign(input,'unionday.in');reset(input);
- assign(output,'unionday.out');rewrite(output);
- read(n);
- for i:=1 to n do
- read(x[i],y[i]);
- m:=0;
- for i:=1 to n do
- for j:=i+1 to n do
- begin
- inc(m);
- a[m]:=i;
- b[m]:=j;
- w[m]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
- end;
- sort(1,m);
- for i:=1 to n do
- begin
- p[i]:=i;
- rank[i]:=0;
- end;
- z:=0;
- cost:=0;
- for i:=1 to m do
- begin
- if find(a[i])<>find(b[i]) then
- begin
- union(a[i],b[i]);
- cost:=cost+w[i];
- end;
- end;
- writeln(cost:0:5);
- end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement