ac1033.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1033;
const
  maxn=18;
  rands=99;
var
  x,y:array[1..maxn]of real;
  dist:array[1..maxn,1..maxn]of real;
  num:array[1..maxn]of byte;
  n,r,t,i,j,k:word;
  ans,s,a1,a2,b1,b2:real;
  aug:boolean;
begin
  repeat
    read(n);
    for i:=1 to n do begin
      read(x[i],y[i]);
      num[i]:=i;
    end;
    for i:=1 to n do
      for j:=1 to n do
        dist[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

    ans:=1e9;
    for r:=1 to rands do begin
      for i:=1 to n do begin
        j:=random(n)+1;
        t:=num[i];num[i]:=num[j];num[j]:=t;
      end;

      repeat
        aug:=false;
        for j:=2 to n do
          for i:=1 to j-1 do begin
            if i=1 then begin a1:=0;b1:=0;end
                   else begin a1:=dist[num[i-1],num[i]];b1:=dist[num[i-1],num[j]];end;
            if j=n then begin a2:=0;b2:=0;end
                   else begin a2:=dist[num[j],num[j+1]];b2:=dist[num[i],num[j+1]];end;
            if a1+a2>b1+b2 then begin
              aug:=true;
              for k:=i to (i+j-1) shr 1 do begin
                t:=num[k];num[k]:=num[i+j-k];num[i+j-k]:=t;
              end;
            end;
          end;
      until not aug;

      s:=0;for i:=2 to n do s:=s+dist[num[i-1],num[i]];
      if s<ans then ans:=s;
    end;
    writeln(ans:0:2);
  until seekeof;
end.