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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// n^2 - na male testy

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

void inline normalizuj(int& a, int& b) {
    int tmp = a;
    a = a < b ? a : b;
    b = tmp < b ? b : tmp;
}

struct Samochod {
    int startX1, startX2, startY1, startY2;
    int koniecX1, koniecX2, koniecY1, koniecY2;
    bool zaparkowany;

    int kolejnoscPoczatkowa, kolejnoscParkowania, wysokosc;

    void norm() {
        normalizuj(startX1, startX2);
        normalizuj(startY1, startY2);
        normalizuj(koniecX1, koniecX2);
        normalizuj(koniecY1, koniecY2);
        wysokosc = startY2 - startY1;
    }
};

Samochod* samochodyPoczatkowa[50000];
Samochod* samochodyKoncowa[50000];
int maksWysokosc[50000];

bool sort1(const Samochod* s1, const Samochod* s2) {
    return s1->startX2 < s2->startX2;
}

bool sort2(const Samochod* s1, const Samochod* s2) {

    if (s1->koniecX1 == s2->koniecX1) {
        return s1->startX2 < s2->startX2;
    }

    return s1->koniecX1 < s2->koniecX1;
}

int main() {

    int licztaTestow;
    scanf("%d", &licztaTestow);

    for (int i = 0; i < 50000; ++i) {
        samochodyPoczatkowa[i] = new Samochod();
    }

    for (int i = 0; i < licztaTestow; ++i) {

        int liczbaSamochodow, wysokoscParkingu;
        scanf("%d%d", &liczbaSamochodow, &wysokoscParkingu);

        for (int j = 0; j < liczbaSamochodow; ++j) {
            maksWysokosc[j] = 0;
            samochodyPoczatkowa[j]->zaparkowany = false;
            scanf("%d%d%d%d", &samochodyPoczatkowa[j]->startX1, &samochodyPoczatkowa[j]->startY1, &samochodyPoczatkowa[j]->startX2, &samochodyPoczatkowa[j]->startY2);
        }
        for (int j = 0; j < liczbaSamochodow; ++j) {
            scanf("%d%d%d%d", &samochodyPoczatkowa[j]->koniecX1, &samochodyPoczatkowa[j]->koniecY1, &samochodyPoczatkowa[j]->koniecX2, &samochodyPoczatkowa[j]->koniecY2);
            samochodyPoczatkowa[j]->norm();
            samochodyKoncowa[j] = samochodyPoczatkowa[j];
        }

        std::sort(samochodyKoncowa, samochodyKoncowa + liczbaSamochodow, sort2);
        for (int j = 0; j < liczbaSamochodow; ++j) {
            samochodyKoncowa[j]->kolejnoscParkowania = j;
        }

        std::sort(samochodyPoczatkowa, samochodyPoczatkowa + liczbaSamochodow, sort1);
        for (int j = 0; j < liczbaSamochodow; ++j) {
            samochodyPoczatkowa[j]->kolejnoscPoczatkowa = j;
        }

        bool parkowanieMozliwe = true;
        for (int j = 0; j < liczbaSamochodow; ++j) {
            Samochod* s = samochodyPoczatkowa[j];
            int wysokosc = s->wysokosc;

            int x1 = liczbaSamochodow - (s->kolejnoscPoczatkowa + 1);
            int x2 = s->kolejnoscParkowania;

            if (x1 < x2) {
                for (int k = s->kolejnoscPoczatkowa + 1; k < liczbaSamochodow; ++k) {
                    if (samochodyPoczatkowa[k]->kolejnoscParkowania < s->kolejnoscParkowania) {
                        int maks = std::max(wysokosc, maksWysokosc[k]);
                        if (maks > wysokoscParkingu - samochodyPoczatkowa[k]->wysokosc) {
                            parkowanieMozliwe = false;
                            break;
                        }
                        maksWysokosc[k] = maks;
                    }
                }
            } else {
                for (int k = 0; k < s->kolejnoscParkowania; ++k) {
                    if (samochodyKoncowa[k]->kolejnoscPoczatkowa > s->kolejnoscPoczatkowa) {
                        int pocz = samochodyKoncowa[k]->kolejnoscPoczatkowa;
                        int maks = std::max(wysokosc, maksWysokosc[pocz]);
                        if (maks > wysokoscParkingu - samochodyPoczatkowa[pocz]->wysokosc) {
                            parkowanieMozliwe = false;
                            break;
                        }
                        maksWysokosc[pocz] = maks;
                    }
                }
            }
        }

        if (parkowanieMozliwe) {
            printf("TAK\n");
        } else {
            printf("NIE\n");
        }
    }

    return 0;
}