1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
program parking; const nmax=100000;//runda 3[B]      14.05.2014
type Ti=longint;
  TSam=record xp,xk,h,klucz,nrsam:Ti end;//xp:przed xk:po przestawieniu
  TabSam = array[1..nmax] of TSam;
var t,n,w:Ti;
  x1,y1,x2,y2,i,ipo,l,lsma,w2:Ti;//pom
  kont:boolean;
  Sam,Spo,Sko:TabSam;//Spo,Sko: elementy(h>w/2) przed i po przestawieniu

Procedure MSort(n:Ti; Var Tab:TabSam);
 Var Le,Ra: Array[1..nmax div 2 +1] of TSam;//pom
{.}Procedure Merge(p,q,r:Ti); Var n1,n2,i,j,k:Ti;
   Begin n1:=q-p+1; n2:=r-q;
    for i:=1 to n1 do Le[i]:=Tab[p+i-1];
    for j:=1 to n2 do Ra[j]:=Tab[q+j];
    Le[n1+1].klucz:=-1;{wartownik} Ra[n2+1].klucz:=-1; i:=1; j:=1;
    for k:=p to r do  if Le[i].klucz>=Ra[j].klucz then
    Begin Tab[k]:=Le[i]; Inc(i) End else Begin Tab[k]:=Ra[j]; Inc(j) End
{-}End;{Merge}
{.}Procedure S(p,r:Ti); Var q:Ti;
   Begin if p<r then Begin q:=(p+r)div 2;S(p,q);S(q+1,r);Merge(p,q,r)End
{.}End;{S}
Begin S(1,n) End;{Msort}

begin
 readln(t);//lzestawów
 for t:=1 to t do
 begin
  readln(n,w); w2:=w div 2;//samochody, szer parkingu
  for i:=1 to n do  with Sam[i] do
  begin
    readln(x1,y1,x2,y2);  nrsam:=i;
    xp:=x1+x2;  h:=abs(y1-y2); klucz:=h //xp=2*(odcieta srodka)
  end; 
  for i:=1 to n do  with Sam[i] do
    begin readln(x1,y1,x2,y2); xk:=x1+x2 end;//dane
  if n=1 then begin writeln('TAK'); exit end;//1 samochód

  MSort(n,Sam);//sortowanie wzgl h
 //generowanie Spo, Sko: tablice o h>w/2
  lsma:=0; //licznik samochodów o h>w/2 
  for i:=1 to n do  with Sam[i] do //ustawienia pocz i konc
  if  Sam[i].h>w2 then
  begin lsma+=1; Spo[lsma]:=Sam[i]; Spo[lsma].klucz:=xp;
    Sko[lsma]:=Sam[i]; Sko[lsma].klucz:=xk;        
  end;
  if lsma=0 then  begin writeln('TAK'); exit end;//wszystkie h<=w/2
  MSort(lsma,Spo); MSort(lsma,Sko);//sortowanie wzgl h
  for i:=1 to lsma do
  if Spo[i].nrsam <> Sko[i].nrsam then
    begin writeln('NIE'); exit end;
  if lsma=n then  begin writeln('TAK'); exit end;//wszystkie h>w/2

  ipo:=n; kont:=true;//porownywanie par
  for l:=1 to lsma do  with Sam[l] do  if kont then
  begin
    while h+Sam[ipo].h<=w  do ipo-=1;
    i:=ipo; 
    while (h+Sam[i].h>w) and (i>lsma) do
    begin 
      if ((xp<Sam[i].xp) xor (xk<Sam[i].xk)) then
        begin writeln('NIE'); kont:=false; exit end
      else i-=1
    end;//i
    if not kont then exit;
  end;//l 
  writeln('TAK')
 end//t
end.