| ||||||||||
| 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