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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdlib.h>


typedef struct
{
	int w1;
	int w2;
	int h1;
	int h2;
}
Offer;

int contain(Offer o1, Offer o2)
{
	if(o1.h1 <= o2.h1 && o1.h2 >= o2.h2 && o1.w1 <= o2.w1 && o1.w2 >= o2.w2)
		return 1;
	return 0;
}

int check_offers(Offer* o, int n)
{
	int* s = (int*)malloc(n*sizeof(int));
	int sn = 0;
	int boss_id = 0;

	// Find potential boss
	for(int i=1; i<n; i++)
	{
		if(!contain(o[boss_id], o[i]))
		{
			if(contain(o[i], o[boss_id]))
			{
				// New boss
				s[sn] = boss_id;
				sn++;
				boss_id = i;
			}
			else
			{
				s[sn] = i;
				sn++;
			}
		}
	}

	// Make sure that the boss is not fake
	for(int i=0; i<sn; i++)
	{
		if(!contain(o[boss_id], o[s[i]]))
		{
			free(s);
			return 0;
		}
	}

	free(s);
	return 1;
}

int main()
{
	int n = 0, t = 0;

	// Main loop
	scanf("%d", &t);

	for(int i=0; i<t; i++)
	{
		scanf("%d", &n);
		Offer* o = (Offer*)malloc(n * sizeof(Offer));

		for(int j=0; j<n; j++)
		{
			Offer* x = &o[j];
			scanf("%d %d %d %d", &(x->w1), &(x->w2), &(x->h1), &(x->h2));
		}

		if(check_offers(o, n))
			printf("TAK\n");
		else
			printf("NIE\n");

		free(o);
	}

	return 0;
}