{ Free Pascal } const n_=1000; {верхня межа n} label NEXTi, {наступний рiвень гiпотез} NEXTh, {наступна гiпотеза} FIN; {кiнець роботи} var a,b,r, {розмiри й орiїнтацiя прямокутникiв} z,u: array[1..n_] of longint;{координати лiвих нижнiх вершин} h: array[1..n_] of byte; {перестановка} x,y: array[0..n_*4+3] of word; {координати вершин границi} t, {площа останнього прямокутника} s, {сума площ перших n прямокутникiв} nsol, {кiлькiсть розв'язкiв} ub: longint; {допомiжна змiнна для обмiну даних} n, n1, {кiлькiсть прямокутникiв, n1=n+1} na, {кiлькiсть вершин ламано∙} k, {парний номер вершини ламано∙ з найменшою абсцисою} i,j,l: byte; {допомiжнi лiчильники} sh: set of byte; {числа з визначеним мўсцем у перестановцў} o: text; {файл вiдповiдi} procedure ROT (j: byte); {Замiна a[j] <-> b[j]} begin ub:=a[j]; a[j]:=b[j]; b[j]:=ub end; procedure SIMPLIFY; {Вилучення зайвих вершин ламано∙} begin k:=1; repeat inc(k) until (k>na) or (y[k]<>b[n1]); k:=k-2; na:=na-k; if k>0 then for j:=1 to na do begin x[j]:=x[j+k]; y[j]:=y[j+k] end; k:=na; repeat dec(k) until (k<1) or (x[k]<>a[n1]); na:=k+1; j:=0; while j+2na); dec(k); na:=na+4; for j:=na downto k+5 do begin x[j] :=x[j-4]; y[j] :=y[j-4] end; x[k+1]:=x[k]; y[k+1]:=u[i]+b[h[i]]; x[k+2]:=z[i]; y[k+2]:=y[k+1]; x[k+3]:=z[i]; y[k+3]:=u[i]; x[k+4]:=x[k+5]; y[k+4]:=u[i]; SIMPLIFY; SIMPLIFY end; BEGIN assign(o,'rectang.in'); reset(o); {Зчитування даних} read(o,n); n1:=n+1; for j:=1 to n1 do read(o,a[j],b[j]); close(o); assign(o,'rectang.out'); rewrite(o); nsol:=0; {Порiвняння розмiрiв i площ} t:=a[n1]*b[n1]; s:=0; for j:=1 to n do begin s:=a[j] *b[j] + s; if ((a[j]>a[n1]) and (a[j]>b[n1])) or (s>t) or ((b[j]>a[n1]) and (b[j]>b[n1])) then goto FIN end; if s<>t then goto FIN; x[1]:=0; x[2]:=0; x[3]:=a[n1]; y[1]:=b[n1]; y[2]:=0; y[3]:=0; na:=3; k:=2; sh:=[]; i:=0; NEXTi: inc(i); h[i]:=0; {Перебiр} NEXTh: if h[i]=0 then repeat inc(h[i]) until (h[i]>n) or not (h[i] in sh) else if r[h[i]] =0 then begin r[h[i]]:=1; ROT(h[i]) end else begin r[h[i]]:=0; ROT(h[i]); repeat inc(h[i]) until (h[i]>n) or not (h[i] in sh); if h[i]>n then begin dec(i); if i=0 then goto FIN; OLD; goto NEXTh end end; {Чи не вийдемо за межi найбiльшого прямокутника?} if (y[k]+b[h[i]]>y[k-1]) or (x[k]+a[h[i]]>a[n1]) then goto NEXTh; NEW; {Чи всi прямокутники використано?} if i1 then begin OLD; goto NEXTh end; {Запис вiдповiдi} inc (nsol); for j:=1 to n do begin if 1