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 <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

class Prostokat {
    public:
        int poz, xdol, ydol, xgora, ygora, w;
        Prostokat(int _poz = 0,int  _xdol = 0,int  _ydol = 0,int  _xgora = 0, int  _ygora = 0) :
           poz(_poz), xdol(_xdol), ydol(_ydol), xgora(_xgora), ygora(_ygora) { w =  ygora - ydol; };

        bool operator < (const Prostokat &other) const {
            if (this->xdol < other.xdol)
                return true;
            if (this->xdol == other.xdol)
                return this->ydol < other.ydol;
            return false;
        };

};

int main() {
    int testy;
    scanf("%d", &testy);

    for (int t = 0; t < testy; ++t) {
        int ile, wys;
        scanf("%d %d", &ile, &wys);

        Prostokat poczatek[50005];
        Prostokat koniec[50005];

        int ostPozycja[50005];

        for (int i = 0; i < ile ; ++i) {
            int xd, yd, xg, yg;
            scanf("%d %d %d %d", &xd, &yd, &xg, &yg);
            Prostokat p(i, xd,yd, xg,yg);
            poczatek[i] = p;
        }

        for (int i = 0; i < ile ; ++i) {
            int xd, yd, xg, yg;
            scanf("%d %d %d %d", &xd, &yd, &xg, &yg);
            Prostokat p(i, xd,yd, xg,yg);
            koniec[i] = p;
        }

//        sort(koniec.begin(), koniec.end());
        sort(koniec, koniec + ile);

        for (int i = 0; i < ile ; ++i) {
           ostPozycja[koniec[i].poz] = i;
        }

        bool czyOK = true;
        for (int i = 0; i < ile; ++i) {
            int &ost = ostPozycja[i];
            if (i == ost) continue;
            if (i < ost) {
                for (int j = i + 1; j <= ost; ++j) {
                   if (poczatek[i].w + poczatek[j].w >  wys) {
                        czyOK = false;
                        goto koniecTestu;
                   }
                }
            } else {
                for (int j = i - 1; j >= ost; --j) {
                   if (poczatek[i].w + poczatek[j].w  >  wys) {
                        czyOK = false;
                        goto koniecTestu;
                   }
                }
            }
        }

        koniecTestu:
        printf("%s\n", czyOK ? "TAK" : "NIE");
    } // test

    return 0;
}