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
#include<cstdio>
#include<algorithm>

using namespace std;

struct glass{
	long long int w_min;
	long long int w_max;
	long long int h_min;
	long long int h_max;	
};

bool por(glass a, glass b){
	if(a.w_min<b.w_min)return true;
	if(a.w_min>b.w_min)return false;

	if(a.w_max<b.w_max)return true;
	if(a.w_max>b.w_max)return false;

	if(a.h_min<b.h_min)return true;
	if(a.h_min>b.h_min)return false;

	if(a.h_max<b.h_max)return true;
	if(a.h_max>b.h_max)return false;
}

glass szyba[100001];

int za_malo_czasu_by_pisac_binary_searcha(int value, int start, int end, int typ){
	for(int i=start; i<end; ++i){
		if(typ==1 && szyba[i].w_min>value)return i;
		if(typ==2 && szyba[i].w_max==value)return i;
		if(typ==3 && szyba[i].h_min>value)return i;
		if(typ==4 && szyba[i].h_max==value)return i;
		if(i==(end-1) && (typ==1 || typ==3))return end;
		if(i==(end-1) && (typ==2 || typ==4))return end+1;
	}
}

glass maj;
int t,n,poczatek,koniec;

int main(){
	scanf("%d",&t);
	for(int test=0; test<t; ++test){
		scanf("%d",&n);
		//Wielkie czyszczenie zmiennych
		maj.w_min=1000000033;
		maj.w_max=0;
		maj.h_min=1000000033;
		maj.h_max=0;
		poczatek=0;
		koniec=n;
		//koniec czyszczenia
		for(int i=0; i<n; ++i){
			scanf("%lld %lld %lld %lld", &szyba[i].w_min, &szyba[i].w_max, &szyba[i].h_min, &szyba[i].h_max);
			if(szyba[i].w_min<maj.w_min)maj.w_min=szyba[i].w_min;
			if(szyba[i].w_max>maj.w_max)maj.w_max=szyba[i].w_max;
			if(szyba[i].h_min<maj.h_min)maj.h_min=szyba[i].h_min;
			if(szyba[i].h_max>maj.h_max)maj.h_max=szyba[i].h_max;
		}
		sort(szyba,szyba+n,por);
		koniec=za_malo_czasu_by_pisac_binary_searcha(maj.w_min,poczatek,koniec,1);
		poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.w_max,poczatek,koniec,2);
		koniec=za_malo_czasu_by_pisac_binary_searcha(maj.h_min,poczatek,koniec,3);
		poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.h_max,poczatek,koniec,4);

		if(koniec<=poczatek){
			printf("NIE\n");
			continue;
		}
		printf("TAK\n");
	}
	return 0;
}