• Открытки и конверты
  POSTCARD
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
Жюри решило поздравить авторов метода Форда-Фалкерсона, алгоритмов Флойда-Беллмана, Кнута-Морриса-Пратта, формы Бэкуса-Науэра, схемы Ривеста-Шамира-Адлемана и других классиков Computer Science с наступающим 4 июля (Днем независимости). Для этого было куплено N открыток и M конвертов. К сожалению, конверты и открытки оказались разных размеров, и некоторые открытки помещаются не во все конверты

Задание
Напишите программу, находящую такое распределение открыток по конвертам, при котором поздравления получат наибольшее число классиков Computer Science. В один конверт разрешается вкладывать не более одной открытки


Входные данные
В первой строке входного файла записаны числа M и N (0≤M,N≤100). Далее записаны высота и ширина каждого из M конвертов, затем – высота и ширина каждой из N открыток. Размеры конвертов и открыток являются натуральными числами, не превосходящими 32767, и разделяются пробелами и/или символами перевода строки

Выходные данные
Выведите в выходной файл целое число K – максимальное количество открыток, которые можно разложить по конвертам. Далее выведите K пар целых чисел, означающих номер открытки и номер конверта, в который ее необходимо положить
 

Например:

POSTCARD.IN
4 4
3 3 141 282 282 141 200 100
3 1 140 280 141 282 201 1

POSTCARD.OUT
4
1 1 2 3 3 2 4 4

Идеи
Набольшее паросочетание, элементарная геометрия

Комментарии
Построим двудольный граф, вершинами первой доли которого являются открытки, вершинами второй доли – конверты, а существование ребра между вершинами двух долей соответствует возможности вложения данной открытки в данный конверт. Тем самым, исходная задача распалась на две. Одна из них состоит в определении возможности поместить один прямоугольник внутрь другого (не забывайте, что открытку в конверт можно вкладывать под углом) и решается с использованием несложных геометрических соображений (см. решение задачи 10 в [Бадин 95]). Другая задача – нахождение наибольшего паросочетания в полученном графе
 

Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}

 program postcard;
 var
   m,n: integer;
   ot,kv: array [1..100,1..2] of longint;
   a: array [1..100,1..100] of boolean;
   vo: array [1..100] of boolean;
   wk,wo: array [1..100] of integer;
 
 procedure ReadAll;
 var  i: Integer;
 begin
   Assign(Input, 'postcard.in');
   Reset(Input);
 
   Read(m,n);
   for i := 1 to m do Read(kv[i,1],kv[i,2]);
   for i := 1 to n do Read(ot[i,1],ot[i,2]);
 
   Close(Input);
 end;
 
 function AddO(o: integer): boolean; forward;
 
 function FreeK(k: integer): boolean;
 begin
   if wk[k]=0 then begin FreeK := true; exit; end;
   if AddO(wk[k]) then FreeK := true else FreeK := false;
 end;
 
 function AddO(o: integer): boolean;
 var
   i: Integer;
 begin
   if vo[o] then begin AddO := false; exit end;
   vo[o] := true;
   for i := 1 to m do if a[o,i] and (wk[i]=0) then begin
     wk[i] := o;
     wo[o] := i;
     AddO := true;
     exit;
   end;
   for i := 1 to m do if a[o,i] and FreeK(i) then begin
     wk[i] := o;
     wo[o] := i;
     AddO := true;
     exit;
   end;
   AddO := false;
   exit;
 end;
 
 function CanPut(ox, oy, kx, ky: longint): boolean;
 var
   nx, ny, _ox, _oy, _kx, _ky, dd, aa, bb: extended;
   oo: longint;
 begin
   if oy>ox then begin
     CanPut := CanPut(oy, ox, kx, ky);
     exit
   end;
   if ky>kx then begin
     CanPut := CanPut(ox, oy, ky, kx);
     exit
   end;
 
   if (kxor((kx*ky)<(ox*oy)) then begin
     CanPut:= false;
     exit;
   end;
 
   if (ox<=kx) and (oy<=ky) then begin
     CanPut := true;
     exit;
   end;
 
   if (ox>kx) then begin
     oo := ox;
     ox := oy;
     oy := oo;
   end;
 
   if (ox>kx) then begin
     CanPut := false;
     exit
   end;
 
   _ox := ox;
   _oy := oy;
   _kx := kx;
   _ky := ky;
 
    dd := _ky*_ky*_oy*_oy - (-(_ox*_ox) + (_ky*_ky))*( ((_ox*_ox)) + (_oy*_oy));
    if dd<0 then begin
      CanPut := false;
      exit
    end;
 
    aa := ((_ky*_oy) + sqrt(dd) )/(((_ox*_ox)) + (_oy*_oy));
    if (aa>=0)and(aa<=1) then begin
      bb := sqrt(1-(aa*aa));
      nx := _ox*aa + _oy*bb;
      ny := _oy*aa + _ox*bb;
 
      if ((abs(ny-_ky)<1e-6)) and ( (_kx>nx) or (abs(nx-_kx)<1e-6) ) then begin
        CanPut := true;
        exit;
      end;
    end;
 
    aa := ((_ky*_oy) - sqrt(dd) )/(((_ox*_ox)) + (_oy*_oy));
    if (aa>=0)and(aa<=1) then begin
      bb := sqrt(1-(aa*aa));
      nx := _ox*aa + _oy*bb;
      ny := _oy*aa + _ox*bb;
      if ((abs(ny-_ky)<1e-6)) and ( (_kx>nx) or (abs(nx-_kx)<1e-6) ) then begin
        CanPut := true;
        exit;
      end;
    end;
 
    CanPut := false;
 end;
 
 procedure Solve;
 var
   i,j: Integer;
 begin
   fillchar(a,sizeof(a),0);
   fillchar(wk,sizeof(wk),0);
   fillchar(wo,sizeof(wo),0);
   for i := 1 to m do for j := 1 to n do begin
     if CanPut(ot[j,1],ot[j,2],kv[i,1],kv[i,2]) then a[j,i] := true;
   end;
 
   for i := 1 to n do begin
     fillchar(vo, sizeof(vo), false);
     AddO(i);
   end;
 end;
 
 procedure Out;
 var
   i, k: longint;
 begin
   Assign(Output, 'postcard.out');
   ReWrite(Output);
 
   k := 0;
   for i := 1 to n do if wo[i]>0 then inc(k);
   WriteLn(k);
   for i := 1 to n do if wo[i]>0 then begin
     Write(i, ' ', wo[i], ' ');
   end;
   WriteLn;
 
   Close(Output);
 end;
 
 begin
   ReadAll;
   Solve;
   Out;
 end.

 

© Особенности национальных задач по информатике