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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stdint.h>
#include <vector>

    struct Rect
    {
        Rect() : x(-1), w(-1), y(-2), h(-1), area(0) {}
        Rect(int x_, int y_, int w_, int h_) : x(x_), w(w_), y(y_), h(h_), area(w_ * h_) {}
        int x, y, w, h;
        uint64_t area;
        inline Rect intersection(Rect & r)
        {
            Rect newRect;
            newRect.x = std::max<int>(x, r.x);
            newRect.y = std::max<int>(y, r.y);
            int x2 = std::min<int>(x + w, r.x + r.w);
            int y2 = std::min<int>(y + h, r.y + r.h);
            newRect.w = x2 - newRect.x; // std::min<int>(x + w - r.x, r.x + r.w - x);
            newRect.h = y2 - newRect.y;// std::min<int>(y + h - r.y, r.x + r.h - y);
            return newRect;
        }

        bool operator==(const Rect & r) const { 
            return (x == r.x && y == r.y && w == r.w && h == r.h); 
        }

        inline Rect subRect(int i) {
            switch(i) {
                case 0: return Rect(x, y, w / 2, h / 2);
                case 1: return Rect(x + w / 2, y, w / 2, h / 2);
                case 2: return Rect(x, y + h / 2, w / 2, h / 2);
                case 3: return Rect(x + w / 2, y + h / 2, w / 2, h / 2);
            }
            return Rect();
        }

        inline bool isNull() { return w < 0 || h < 0; }

        bool operator< (const Rect & r) const {
            return area < r.area;
        }

        bool contains(const Rect & r) const {
            return r.x >= x && r.y >= y && r.x + r.w <= x + w && r.y + r.h <= y + h;
        }
    };


int main(int argc, char* argv[])
{
    int t, n, w1, w2, h1, h2;

    std::vector<Rect> vect;
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        vect.clear();
        scanf("%d", &n);
        Rect bigRect(0,0,0,0);
        for (int j = 0; j < n; ++j) {
            scanf("%d%d%d%d", &w1, &w2, &h1, &h2);
            Rect currentRect(w1, h1, w2 - w1 + 1, h2 - h1 + 1);
            vect.push_back(currentRect);
            if (bigRect < currentRect)
                bigRect = currentRect;
        }
        bool retVal = true;
        for (int i = 0; i < vect.size(); ++i)
        {
            if ( !bigRect.contains(vect[i]) )
            {
                retVal = false;
                break;
            }
        }
        if (retVal)
            printf("TAK\n");
        else
            printf("NIE\n");
    }
	return 0;
}