比赛 |
noip20081103 |
评测结果 |
AAWWWWWWWA |
题目名称 |
放养奶牛 |
最终得分 |
30 |
用户昵称 |
lc |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2008-11-03 22:02:54 |
显示代码纯文本
program p2;
var
n:longint;
ans:real;
f:array[1..102,1..40] of real;
s:array[1..102,0..80] of longint;
function dis(xx,yy,x,y:real):real;
begin
dis:=sqrt(sqr(xx-x)+sqr(yy-y));
end;
procedure init;
var
i,j:longint;
begin
readln(N);
for i:=1 to n do
begin
read(s[i,0]);
for j:=1 to s[i,0]*2 do
read(s[i,j]);
end;
end;
procedure main;
var
i,j,d1,d2:longint;
tm,ans,x,y,xx,yy:real;
begin
inc(n); s[n]:=s[1];
for i:=2 to n do
for d1:=1 to s[i,0] do
begin
f[i,d1]:=maxlongint div 2;
x:=s[i,d1*2-1]; y:=s[i,d1*2];
j:=i-1;
for d2:=1 to s[j,0] do
begin
xx:=s[j,d2*2-1]; yy:=s[j,d2*2];
if (xx<>x) or (yy<>y)
then
begin
tm:=f[j,d2]+dis(xx,yy,x,y);
if tm<f[i,d1] then f[i,d1]:=tm;
end;
end;
end;
ans:=maxlongint;
for i:=1 to s[n,0] do
if f[n,i]<ans then ans:=f[n,i];
writeln(trunc(ans*100));
end;
begin
assign(input,'cowties.in');
assign(output,'cowties.out');
reset(input); rewrite(output);
init;
main;
close(input); close(output);
end.