Help!(p1065)
Послано
qaztz 4 апр 2002 18:48
I've got trouble in problem 1065.
Here is my program:
{$q+,n+}
var n,m,a,d,e:integer; min,j:extended;
b:array[0..50,1..2] of extended;
c:array[1..1000,1..2] of extended;
f:array[1..50,1..50] of boolean;
g:array[0..50] of shortint;
h:array[1..50,1..2] of extended;
i:array[1..50,1..50] of extended;
begin
assign(input,''); reset(input);
assign(output,''); rewrite(output);
readln(n,m);
for a:=1 to n do readln(b[a,1],b[a,2]);
for a:=1 to m do readln(c[a,1],c[a,2]);
for a:=1 to n do for d:=1 to n do
if a<>d then begin
f[a,d]:=true;
for e:=1 to m do
if (b[d,1]-b[a,1])*(c[e,2]-b[a,2])-(b[d,2]-b[a,2])*(c[e,1]-b
[a,1])>=0
then begin
f[a,d]:=false; break;
end;
end;
for a:=1 to n-1 do for d:=a+1 to n do begin
i[a,d]:=sqrt(sqr(b[a,1]-b[d,1])+sqr(b[a,2]-b[d,2]));
i[d,a]:=i[a,d];
end;
for a:=1 to n do g[a]:=a;
min:=1e20;
for a:=1 to n do begin
fillchar(h,sizeof(h),0);
for d:=2 to n do begin
if f[g[1],g[d]] then h[d,1]:=i[g[1],g[d]]
else h[d,1]:=1e20;
h[d,2]:=1e20;
end;
for d:=3 to n do for e:=2 to d-1 do
if f[g[e],g[d]] then begin
if h[e,1]<h[e,2] then j:=h[e,1]
else j:=h[e,2];
if h[d,2]>j+i[g[e],g[d]] then h[d,2]:=j+i[g[e],g[d]];
end;
for d:=3 to n do
if f[g[d],g[1]] and(h[d,2]+i[g[1],g[d]]<min) then
min:=h[d,2]+i[g[1],g[d]];
for d:=1 to n do g[d-1]:=g[d];
g[n]:=g[0];
end;
writeln(min:0:2);
close(input); close(output);
end.
Thank you!