比赛 20100422 评测结果 AAA
题目名称 烦人的幻灯片 最终得分 100
用户昵称 ybh 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-04-22 11:13:40
显示代码纯文本
program slides;
var
  limit,flow:array[0..100,0..100] of integer;
  check:array[0..100] of boolean;
  last,next,next1:array[0..100] of integer;
  x1,x2,x3,y1,y2,y3:array[0..100] of integer;
  n,i,j,ans,i1:integer;

procedure maxflow;
begin
  ans:=0;
  fillchar(flow,sizeof(flow),0);
  fillchar(next,sizeof(next),0);
  repeat
    fillchar(last,sizeof(last),0);
    fillchar(check,sizeof(check),false);
    last[1]:=32767;
    repeat
      i:=0;
      repeat
        inc(i);
      until (i>n*2+2) or ((last[i]<>0) and (not check[i]));
      if i>n*2+2
        then break;
      for j:=1 to n*2+2 do
        if last[j]=0 then
          if flow[i,j]<limit[i,j] then
            last[j]:=i
          else
            if flow[j,i]>0
              then last[j]:=-i;
      check[i]:=true;
    until last[n*2+2]<>0;
    if last[n*2+2]=0
      then break;
    i:=n*2+2;
    repeat
      j:=i;
      i:=abs(last[j]);
      if last[j]>0 then
      begin
        inc(flow[i,j]);
        next[i]:=j
      end
      else
      begin
        dec(flow[j,i]);
      end
    until i=1;
    inc(ans);
  until false;
end;

begin
  assign(input,'slides.in');
  reset(input);
  assign(output,'slides.out');
  rewrite(output);
  readln(n);
  for i:=2 to n+1 do
    readln(x1[i],x2[i],y1[i],y2[i]);
  for i:=2 to n+1 do
    readln(x3[i],y3[i]);
  fillchar(limit,sizeof(limit),0);
  fillchar(flow,sizeof(flow),0);
  for i:=2 to n+1 do
    for j:=2 to n+1 do
    begin
      if (x1[i]<=x3[j])and(x3[j]<=x2[i])and(y1[i]<=y3[j])and(y3[j]<=y2[i]) then
      begin
        limit[i,n+j]:=1;
      end
    end;
  for i:=2 to n+1 do
  begin
    limit[1,i]:=1;
    limit[n+i,n*2+2]:=1;
  end;
  maxflow;
  fillchar(next1,sizeof(next1),0);
  if ans=n then
  begin
    next1:=next;
    for i:=2 to n+1 do
    begin
      i1:=next1[i];
      limit[i,i1]:=0;
      maxflow;
      if ans=n then
      begin
        writeln('None');
        close(input);
        close(output);
        halt
      end
      else
        limit[i,i1]:=1;
    end;
    for i:=2 to n+1 do
      writeln(chr(63+i),' ',next1[i]-(n+1));
  end
  else
    writeln('None');
  close(input);
  close(output)
end.