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

using namespace std;

bool debug = false;


class samochod
{
    public:
    int wysokosc;
    int bazpoz;
    int docelpoz;
    int zostanie;
    char przesun;
    void poczatkowe()
    {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        if (debug == true) cout << " poczatkowe wczytane dane " << x1 <<  " " <<  y1 << " " << x2 << " "<< y2 << endl;
        if (y1 < y2) wysokosc = y2 - y1;
        else wysokosc = y1 - y2;
        if (x1 < x2) bazpoz = x1;
        else bazpoz = x2;
    }
    void ostateczne()
    {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        if (debug == true) cout << " ostatecne wczytane dane " << x1 <<  " " <<  y1 << " " << x2 << " "<< y2 << endl;
        if (x1 < x2) docelpoz = x1;
        else docelpoz = x2;
        if (bazpoz < docelpoz) przesun = 'p';
        if (bazpoz > docelpoz) przesun = 'l';
        if (bazpoz == docelpoz) przesun = 'z';
    }
};



char sprawdz();
bool porownaj(samochod a, samochod b);



char sprawdz()
{
    int ilesam = 0, wysokoscpark = 0, przejazd = 0;
    scanf("%d %d", &ilesam, &wysokoscpark);
    if (debug == true) cout << ilesam << "  " << wysokoscpark << endl;
    samochod tab[ilesam];
    for (int i = 0; i < ilesam; i++) tab[i].poczatkowe();
    for (int i = 0; i < ilesam; i++)
    {
        tab[i].ostateczne();
        tab[i].zostanie = wysokoscpark - tab[i].wysokosc;
        if (tab[i].zostanie < przejazd && i == 0) przejazd = tab[i].zostanie;
    }

    sort(tab, tab + ilesam, porownaj);
    for (int i = 0; i < ilesam; i++)
    {
        if (debug == true)
        {
            cout << "Samochód nr " << i << "stoi na" << tab[i].bazpoz << " ma wysokosc " << tab[i].wysokosc << " jedzie na " << tab[i].przesun << " aż dojedzie do "<< tab[i].docelpoz << " a żeby go minąć zostanie" << tab[i].zostanie << endl;
        }
        //if (tab[i].przesun != 'z')
        if (tab[i].wysokosc >= przejazd || tab[i].przesun != 'z')
        {
            if (tab[i].przesun == 'l')
            {
                int baza = i - 1;
                while ((tab[i].docelpoz >= tab[baza].bazpoz) && baza >= 0)
                {
                    if (tab[i].wysokosc > tab[baza].zostanie) return ('n');
                    baza --;
                }
            }
            if (tab[i].przesun == 'p')
            {
                int baza = i + 1;
                while ((tab[i].docelpoz <= tab[baza].bazpoz) && baza < ilesam)
                {
                    if (tab[i].wysokosc > tab[baza].zostanie) return ('n');
                    baza ++;
                }
            }
        }
    }

    return ('t');
}


bool porownaj(samochod a, samochod b)
{
    if (a.bazpoz < b.bazpoz) return true;
    return false;
}


int main(int argc, char *argv[])
{
    if (argc > 1) debug = true;
    int ileserii = 0;
    scanf("%d", &ileserii);
    if (debug == true) cout << "będzie" << ileserii << endl;
    char wynik;
    for (int seria = 1; seria <= ileserii; seria++)
    {
        wynik = sprawdz();
        if (wynik == 't') puts("TAK");
        if (wynik == 'n') puts("NIE");
    }
    return 0;
}