Cod sursa(job #77878)

Utilizator crawlerPuni Andrei Paul crawler Data 15 august 2007 00:11:18
Problema Adapost Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.84 kb
const Inf:real=10e12; {Nu garantez ca merge la fel pe linux}
      eps=0.00001;
      MaxN=400+10;
var cap:array[0..2*MaxN,0..2*MaxN] of byte;
cost,dist:array[0..2*MaxN,0..2*MaxN] of real;
cd,t,leg:array[0..2*MaxN] of longint;
mark:array[0..2*MaxN] of boolean;
c,xf,yf,xv,yv:array[0..2*MaxN] of real;
a:array[0..MaxN*MaxN] of real;
p,u,dest,i,j,k,m,n,nr:longint;
rez,MaxD:real;
bun:boolean;

procedure baga(k:longint);
begin
 inc(nr); mark[k]:=true; cd[nr]:=k;
end;

procedure relax(k,i:longint);
begin
if (cap[k,i]=1) and (cost[k,i]+c[k]<c[i]) then
                        begin
                        t[i]:=k; c[i]:=c[k]+cost[k,i];
                        if not mark[i] and (i<>dest) then baga(i);
                        end;
end;

procedure expand(k:longint);
var st,i,j:longint;
begin
if c[k]>=c[dest] then exit;
if k<=n then
        for i:=n+1 to 2*n do relax (k,i);
relax(k, leg[k]); relax(k, dest);
end;

procedure drum_minim(st:longint);
var i,j,pmin,pmin2:longint;
min:real;
begin
fillchar(mark,dest,false);
for i:=1 to dest do c[i]:=inf;
t[st]:=0;
nr:=0; c[st]:=0; baga(st);
repeat
 pmin:=random(nr)+1; //asa, ca sa nu ma mai chinui
 expand(cd[pmin]); mark[cd[pmin]]:=false;
 cd[pmin]:=cd[nr]; dec(nr);
until (nr=0) or (c[dest]<eps);
if c[dest]<inf then rez:=rez+c[dest]
               else bun:=false;
i:=dest;
while i<>0 do
 begin
 j:=t[i]; cap[j][i]:=0; cap[i][j]:=1;
 if (i>n) and (j<=n) then leg[i]:=j
                     else leg[j]:=i;
 i:=j;
 end;
end;

procedure solve;
var i,j:longint;
begin
rez:=0; dest:=2*n+1;
fillchar(cap, sizeof(cap), 0);
for i:=1 to n do
 begin
 cap[0,i]:=1; cap[i+n,2*n+1]:=1;
 end;
for i:=1 to n do
 for j:=n+1 to n+n do
 if dist[i,j-n]<=MaxD then cap[i,j]:=1;
i:=1; bun:=true;
while (i<=n) and bun do
 begin
 drum_minim(i); inc(i);
 end;
end;

procedure sort(l,r:longint);
var i,j: longint;
x,y:real;
begin
i:=l; j:=r;
x:=a[(l+r) div 2];
repeat
 while a[i]<x do inc(i);
 while x<a[j] do dec(j);
 if (i<=j) then
           begin
           y:=a[i]; a[i]:=a[j]; a[j]:=y;
           inc(i); dec(j);
           end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
assign(input,'adapost.in'); reset(input);
assign(output,'adapost.out'); rewrite(output);
read(n);
for i:=1 to n do read(xv[i], yv[i]);
for i:=1 to n do read(xf[i], yf[i]);
for i:=1 to n do
 for j:=1 to n do
  begin
  dist[i,j]:=sqrt(sqr(xv[i]-xf[j])+sqr(yv[i]-yf[j]));
  a[(i-1)*n+j]:=dist[i,j];
  end;
sort(1,n*n);
p:=1; u:=n*n;
while p<u do
 begin
 MaxD:=a[(p+u) div 2];
 solve;
 if bun then u:=(p+u) div 2
        else p:=(p+u) div 2+1;
 end;
for i:=1 to n do
 for j:=n+1 to 2*n do
  begin
  cost[i,j]:=dist[i,j-n];
  cost[j,i]:=-cost[i,j];
  end;
// exit;
MaxD:=a[u];
solve;
writeln(a[u]:5:5,' ',rez:5:5);
close(input); close(output);
end.