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
#include <cstdio>
#include<algorithm>
using namespace std;

struct x{
	int Wmin; int Wmax; int Hmin; int Hmax;
};

int ileT, ile;
x t[100005], ob;
bool ok[100005], res;

int main(){
	scanf("%d", &ileT);
	for(int q=0; q<ileT; q++){
		res=false;
		scanf("%d", &ile);
		for(int i=0; i<ile; i++){
			scanf("%d %d %d %d", &t[i].Wmin, &t[i].Wmax, &t[i].Hmin, &t[i].Hmax);
		}
		ob.Wmin=t[0].Wmin; ob.Wmax=t[0].Wmax; 
		ob.Hmin=t[0].Hmin; ob.Hmax=t[0].Hmax;
		ok[0]=true;
		for(int i=1; i<ile; i++){
		//	printf("KOLEJKA D %d:    %d %d %d %d\n",i,ob.Wmin,ob.Wmax,ob.Hmin,ob.Hmax);
			if(ob.Wmin>=t[i].Wmin && ob.Hmin>=t[i].Hmin &&
			   ob.Wmax<=t[i].Wmax && ob.Hmax<=t[i].Hmax)
			   {
				ok[i]=true;
				//printf("--> %d jest ok\n",i);
			}
			else
				ok[i]=false;
			ob.Wmin=min(ob.Wmin, t[i].Wmin);
			ob.Wmax=max(ob.Wmax, t[i].Wmax);
			ob.Hmin=min(ob.Hmin, t[i].Hmin);
			ob.Hmax=max(ob.Hmax, t[i].Hmax);
		}
		if(ok[ile-1]) {
			res=true;
		}
		ob.Wmin=t[ile-1].Wmin; ob.Wmax=t[ile-1].Wmax; 
		ob.Hmin=t[ile-1].Hmin; ob.Hmax=t[ile-1].Hmax;
		for(int i=ile-1; i>-1; i--){
			//printf("KOLEJKA P %d:    %d %d %d %d\n",i,ob.Wmin,ob.Wmax,ob.Hmin,ob.Hmax);
			if(ob.Wmin>=t[i].Wmin && ob.Hmin>=t[i].Hmin &&
			   ob.Wmax<=t[i].Wmax && ob.Hmax<=t[i].Hmax && ok[i])
				{
					res=true;
					//printf("<-- %d jest ok\n",i);
					break;
				}
			ob.Wmin=min(ob.Wmin, t[i].Wmin);
			ob.Wmax=max(ob.Wmax, t[i].Wmax);
			ob.Hmin=min(ob.Hmin, t[i].Hmin);
			ob.Hmax=max(ob.Hmax, t[i].Hmax);
		}
		if(res)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}