比赛 noip20081103 评测结果 AWTTTTTTTA
题目名称 放养奶牛 最终得分 20
用户昵称 苏轼 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-03 20:40:31
显示代码纯文本
program cch(input,output);
const
 maxf=10000000000;
type
 sz=record
     num:integer;
     x:array[1..40] of integer;
     y:array[1..40] of integer;
    end;
var
 i,n,s,k,q,j:integer;
 ans,min,tmp,h:real;
 a:array[1..101] of sz;
 f:array[1..101,1..1600] of real;
 ch:array[1..101] of integer;

procedure search(k:integer);
var
 i:integer;
begin
 if k=n+1 then
  begin
   if h<ans then ans:=h;
   exit;
  end;
 if h>=ans then exit;
 for i:=1 to ch[k] do
  begin
   h:=h+f[k,i];
   search(k+1);
   h:=h-f[k,i];
  end;
end;

begin
 assign(input,'cowties.in');
 assign(output,'cowties.out');
 reset(input);
 rewrite(output);
 readln(n);
 for i:=1 to n do
  begin
   read(s);
   a[i].num:=s;
   for j:=1 to s do read(a[i].x[j],a[i].y[j]);
  end;
 a[i+1]:=a[1];
 for i:=1 to n do
  begin
   ch[i]:=0;
   for k:=1 to a[i].num do
    for q:=1 to a[i+1].num do
     begin
      inc(ch[i]);
      f[i,ch[i]]:=sqrt(sqr(a[i].x[k]-a[i+1].x[q])+sqr(a[i].y[k]-a[i+1].y[q]));
     end;
  end;
 ans:=maxf;
 h:=0;
 search(1);
 write(trunc(ans*100));
 close(input);
 close(output);
end.