Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
kruscal32Ms!program ss; type point=record x,y:longint; end; bian=record x,y:longint; w:double; end; var a:array[1..200] of point; e:array[1..100000] of bian; father:array[1..200] of longint; i,j,k,m,n,s,t,x,y,z,l:longint; dist:double; function get(x,y:longint):double; begin exit(sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y))); end; procedure qsort(l,r:longint); var i,j,p:longint; t,mid:double; begin i:=l; j:=r; mid:=e[(l+r) shr 1].w; repeat while e[i].w<mid do inc(i); while e[j].w>mid do dec(j); if i<=j then begin p:=e[i].x; e[i].x:=e[j].x; e[j].x:=p; p:=e[i].y; e[i].y:=e[j].y; e[j].y:=p; t:=e[i].w; e[i].w:=e[j].w; e[j].w:=t; inc(i); dec(j); end; until i>j; if j>l then qsort(l,j); if i<r then qsort(i,r); end; function getfather(v:longint):longint; begin if father[v]=v then exit(v); father[v]:=getfather(father[v]); exit(father[v]); end; begin l:=0; while true do begin readln(n); k:=0; inc(l); if n=0 then halt; for i:=1 to n do readln(a[i].x,a[i].y); for i:=1 to n do for j:=1 to n do if i<>j then begin dist:=get(i,j); inc(k); with e[k] do begin e[k].x:=i; e[k].y:=j; e[k].w:=dist; end; end; for i:=1 to n do father[i]:=i; qsort(1,k); for i:=1 to k do begin x:=getfather(e[i].x); y:=getfather(e[i].y); father[x]:=y; getfather(1); getfather(2); if father[1]=father[2] then begin writeln('Scenario #',l); writeln('Frog Distance = ',e[i].w:0:3); writeln; break; end; end; end; end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator