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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

class Abc {
    public:
        unsigned int min, max;
        bool operator < (const Abc &other) const {
//            printf("--> this->min = %d other->min = %d\n", this->min, other.min);
            if (this->min < other.min)
                return true;
            if (this->min == other.min)
                return this->max > other.max;
            return false;
        }

        bool operator == (const Abc &other) const {
            return this->min == other.min && this->max == other.max;
        }
};

class Dfg {
    public:
        Abc dl, wys;

        bool operator < (const Dfg & other) const {
            if (this->dl < other.dl)
                return true;
            if (this->dl == other.dl)
                return this->wys < other.wys;
            return false;
        }
        void print() {
            printf("%d, %d, %d, %d\n", dl.min, dl.max, wys.min, wys.max);
        }
};

bool czyPrzecina(const Dfg *akt, const Dfg *nast) {
return
       ( (akt->dl.min <= nast->dl.min && nast->dl.min <= akt->dl.max) ||
             (nast->dl.min <= akt->dl.min && akt->dl.min <= nast->dl.max) ) &&
       ( (akt->wys.min <= nast->wys.min && nast->wys.min <= akt->wys.max) ||
             (nast->wys.min <= akt->wys.min && akt->wys.min <= nast->wys.max) );
}

int main() {
    unsigned int testy;
    scanf("%d", &testy);
    for (unsigned int t = 0 ; t < testy; ++t) {
        unsigned int zak;
        scanf("%d", &zak);
        vector<Dfg> w(zak);
        for (unsigned int z = 0; z < zak; ++z) {
            scanf("%d %d %d %d", &w[z].dl.min, &w[z].dl.max, &w[z].wys.min, & w[z].wys.max);
        }
//        printf("before sort ---\n");
//        for (unsigned int z = 0; z < zak; ++z) w[z].print();
//        printf("-- ---\n");

        sort(w.begin(), w.end());

//        printf("after sort\n");
//        for (unsigned int z = 0; z < zak; ++z) w[z].print();
//        printf("-- ---\n");


        Dfg pier = w[0];
        Dfg ost = w[zak - 1];

        if (pier.dl.min <= ost.dl.min && pier.dl.max >= ost.dl.max &&
            pier.wys.min <= ost.wys.min && pier.wys.max >= ost.wys.max) {
//            pier.print();
//            ost.print();
            printf("TAK\n");
        } else {
            bool przecina = true;
            for (unsigned int z = 0; z < zak - 1; ++z) {
                const Dfg *akt = &w[z];
                const Dfg *nast = &w[z+1];

                if (czyPrzecina(akt,nast)) {
                    przecina = true;
                } else {
                    przecina = false;
                    for (unsigned int o = 0; o < zak - 1; ++o) {
                        if  (o == z || o == z + 1) continue;
                        const Dfg *tmp = &w[o];
                        if (czyPrzecina(akt, tmp)) {
                            przecina = true;
                            break;
                        }
                    }

                    if (przecina == false)
                        break;
                }
            }
            printf("%s\n", przecina ? "NIE" : "TAK");
        }

    }
    return 0;
}