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
/*
 * Potyczki Algorytmiczne 2014
 * Round 1 - division B (aka Quest for a cool t-shirt)
 *
 * Author: Mateusz (jam231) Jany 
 */
#include <iostream>
#include <stdint.h>

using namespace std;

static const int buffer_size = 1024 * 8;
static char buffer[buffer_size] = {0};

struct point
{
	int32_t w_1,w_2,h_1,h_2;
};

inline void lower_bound_for(point& candidate, point& lower_bound)
{
	//point new_lower_bound;
	// Why struct initializers doesn't work when sending to sio2.mimuw.edu.pl ? :-( 
	lower_bound.w_1 = std::min(candidate.w_1, lower_bound.w_1);
	lower_bound.w_2 = std::max(candidate.w_2, lower_bound.w_2);
	lower_bound.h_1 = std::min(candidate.h_1, lower_bound.h_1);
	lower_bound.h_2 = std::max(candidate.h_2, lower_bound.h_2);
	//return new_lower_bound;
}

inline bool encloses(const point& p1, const point& p2)
{
	return (p1.w_1 <= p2.w_1 && p2.w_2 <= p1.w_2 && p1.h_1 <= p2.h_1 && p2.h_2 <= p1.h_2);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.rdbuf()->pubsetbuf(buffer, buffer_size);

	int t, n;
	point candidate, lower_bound;
	bool do_we_have_a_winner;	
	cin >> t;

	while(t--)
	{
		cin >> n;
		n -= 1;
		cin >> lower_bound.w_1 >> lower_bound.w_2 >> lower_bound.h_1 >> lower_bound.h_2;
		do_we_have_a_winner = true;
		
		while(n--)
		{
			cin >> candidate.w_1 >> candidate.w_2 >> candidate.h_1 >> candidate.h_2;
			/*
			 * we have 3 possibilities: 
			 *   I)  candidate majorizes_or_eq lower_bound => lower_bound := candidate and do_we_have_a_winner := true
			 *   II) lower_bound majorizes candidate => nothing
			 *   III)neither I) or II) => lower_bound := lower_bound_for(candidate, lower_bound) and do_we_have_a_winner := true   
			 */
			// I)

			if(encloses(candidate, lower_bound))
			{
				do_we_have_a_winner = true;
				lower_bound = candidate;
			} 
			else if(!encloses(lower_bound, candidate))
			{
				do_we_have_a_winner = false;
				lower_bound_for(candidate, lower_bound);
			}
		}
		cout << (do_we_have_a_winner ? "TAK\n" : "NIE\n");

	}

	return 0;
}