比赛 20100422 评测结果 C
题目名称 烦人的幻灯片 最终得分 0
用户昵称 Achilles 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-04-22 10:02:06
显示代码纯文本
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program slides;
var
  max,i,n,j,x,y,p,jiong:longint;
  sz:array[0..101]of record
    xmin,xmax,ymin,ymax:longint;
  end;
  c,g,f:array[0..101,0..101]of integer;
procedure networkg;
var
  i,j:integer;
begin
  for i:=1 to 101 do
    for j:=1 to 101 do
      g[i,j]:=c[i,j]-f[i,j];
end;
procedure path;
var
  d,f2:array[1..1000]of integer;
  p1,p2,p3,i,p,pp,min:integer;
begin
  p1:=0;
  p2:=1;
  d[1]:=1;
  f2[1]:=0;
  p:=0;
  while p1<p2 do
  begin
    p1:=p1+1;
    for i:=1 to 101 do
    begin
      if (g[d[p1],i]>0)or(g[i,d[p1]]>0) then begin
        p2:=p2+1;
        d[p2]:=i;
        f2[p2]:=p1;
        if i=101 then begin
          min:=32767;
          p3:=p2;
          pp:=0;
          while f2[p3]<>0 do
          begin
            if (g[d[p3],d[f2[p3]]]<c[d[p3],d[f2[p3]]])and(g[d[p3],d[f2[p3]]]<min) then min:=g[d[p3],d[f2[p3]]];
            if (g[d[f2[p3]],d[p3]]>0)and(g[d[f2[p3]],d[p3]]<min) then min:=g[d[f2[p3]],d[p3]];
            if ((g[d[p3],d[f2[p3]]]=c[d[p3],d[f2[p3]]])and(c[d[p3],d[f2[p3]]]<>0))or(g[d[f2[p3]],d[p3]]=0)then begin
              pp:=1;
              break;
            end;
            p3:=f2[p3];
          end;
          if pp=0 then begin
            p3:=p2;
            while f2[p3]<>0 do
            begin
              f[d[f2[p3]],d[p3]]:=f[d[f2[p3]],d[p3]]+min;
              f[d[p3],d[f2[p3]]]:=f[d[p3],d[f2[p3]]]-min;
              p3:=f2[p3];
              p:=1;
            end;
          end;
          if p=1 then break;
          p2:=p2-1;
        end;
      end;
    end;
    if p=1 then break;
  end;
  if p=0 then jiong:=1;
end;

begin
  fillchar(c,sizeof(c),0);
  fillchar(g,sizeof(g),0);
  fillchar(f,sizeof(f),0);
  assign(input,'slides.in');
  assign(output,'slides.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=95 to 94+n do
    readln(sz[i+1].xmin,sz[i+1].xmax,sz[i+1].ymin,sz[i+1].ymax);
  for j:=1 to n do
  begin
    readln(x,y);
    for i:=95 to 94+n do
    begin
      if (sz[i+1].xmin<=x)and(sz[i+1].xmax>=x)and(sz[i+1].ymin<=y)and(sz[i+1].ymax>=y) then begin
        c[i+1,j+1]:=1;
      end;
    end;
  end;
  for i:=1 to n do
  begin
    c[0+1,94+i+1]:=100;
    c[i+1,100+1]:=100;
  end;
  jiong:=0;
  while jiong=0 do
  begin
    networkg;
    path;
  end;
  max:=0;
  for i:=2 to n+1 do
    max:=max+f[1,i];
  if max=n then begin
    for i:=66 to 91 do
      for j:=2 to 27 do
      begin
        if f[i,j]=1 then begin
          writeln(chr(i-1),' ',j-1);
        end;
      end;
  end
  else writeln('None');
  close(input);
  close(output);
end.