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
//Adrian Naruszko
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>

#define MAX 100009
#define F first
#define S second
#define MP make_pair

using namespace std;
typedef pair <int, int> pii;
vector <pii> x, y;
int match[MAX];
int JEDEN = 1, DWA = 2, TRZY = 4, CZTERY = 8;
int bylo[MAX];

void liczDla(int mini, int maxi, vector <pii> v, int raz, int dwa){

    int pos = 0;
    while(pos < v.size() && v[pos].F == mini){ /// jesli firma jest skrajna to daje jej +1, jesli na koncu uzyska 4 to byla wszedzie
        match[v[pos].S] |= raz;
        //printf("nabijam %d\n", v[pos].S);
        pos++;
    }
    pos = v.size() - 1;
    while(pos >= 0 && v[pos].F == maxi){
        match[v[pos].S] |= dwa;
        //printf("nabijam %d\n", v[pos].S);
        pos--;
    }
}

int main (){
    int t;
    scanf("%d", &t);
    int n = 0;
    while(t--){
        x.clear();
        y.clear();
        for(int i=0; i<=n; i++)match[i] = 0;
        int a, b;
        scanf("%d", &n);
        for(int i=1; i<=n; i++){ /// wczytuje, dla kazdego pamietam wartosc i numer firmy
            scanf("%d%d", &a, &b);
            x.push_back(MP(a, i));
            x.push_back(MP(b, i));
            scanf("%d%d", &a, &b);
            y.push_back(MP(a, i));
            y.push_back(MP(b, i));
        }

        sort(x.begin(), x.end()); /// surtuje wymiary, jesli jakas firma jest na poczatku i na koncu to wygrywa
        sort(y.begin(), y.end()); /// musi sie zgadzac dla obu wymiarow

        int minX, maxX, minY, maxY; /// ustalam skrajne wartosci
        minX = x[0].F; maxX = x.back().F;
        minY = y[0].F; maxY = y.back().F;

        liczDla(minX, maxX, x, JEDEN, DWA);
        liczDla(minY, maxY, y, TRZY, CZTERY);

        bool istnieje = false;

        for(int i=1; i<=n; i++){
            if(match[i] & JEDEN && match[i] & DWA && match[i] & TRZY && match[i] & CZTERY){
                istnieje = true;
            }
        }

        printf(istnieje ? "TAK\n" : "NIE\n");
    }
}