#define debug if(0) // Grzegorz Guspiel #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<int(n);++i) #define SIZE(c) ((int)((c).size())) #define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) #define ALL(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define st first #define nd second template<typename T> void maxE(T& a, const T& b) { a = max(a, b); } template<typename T> void minE(T& a, const T& b) { a = min(a, b); } const int MAXN = 100 * 1000 + 1; const int INF = 1000 * 1000 * 1000 + 1; int n; int w1[MAXN]; int w2[MAXN]; int h1[MAXN]; int h2[MAXN]; int w1Min[MAXN]; int w2Max[MAXN]; int h1Min[MAXN]; int h2Max[MAXN]; int main() { ios_base::sync_with_stdio(0); int z; cin >> z; while(z--) { cin >> n; REP (i, n) cin >> w1[i] >> w2[i] >> h1[i] >> h2[i]; w1Min[n] = h1Min[n] = INF; w2Max[n] = h2Max[n] = -INF; for (int i = n - 1; i >= 0; i--) { w1Min[i] = min(w1[i], w1Min[i + 1]); h1Min[i] = min(h1[i], h1Min[i + 1]); w2Max[i] = max(w2[i], w2Max[i + 1]); h2Max[i] = max(h2[i], h2Max[i + 1]); } bool found = 0; int w1MinLeft = INF; int h1MinLeft = INF; int w2MaxLeft = -INF; int h2MaxLeft = -INF; REP (i, n) { bool foundHere = 1; if (w1[i] > min(w1MinLeft, w1Min[i + 1])) foundHere = 0; if (h1[i] > min(h1MinLeft, h1Min[i + 1])) foundHere = 0; if (w2[i] < max(w2MaxLeft, w2Max[i + 1])) foundHere = 0; if (h2[i] < max(h2MaxLeft, h2Max[i + 1])) foundHere = 0; if (foundHere) { debug cout << "found " << i << endl; debug cout << "w1[i] " << w1[i] << " w1MinLeft " << w1MinLeft << endl; found = 1; } minE(w1MinLeft, w1[i]); minE(h1MinLeft, h1[i]); maxE(w2MaxLeft, w2[i]); maxE(h2MaxLeft, h2[i]); } if (found) cout << "TAK" << endl; else cout << "NIE" << endl; } return 0; }
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 | #define debug if(0) // Grzegorz Guspiel #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<int(n);++i) #define SIZE(c) ((int)((c).size())) #define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) #define ALL(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define st first #define nd second template<typename T> void maxE(T& a, const T& b) { a = max(a, b); } template<typename T> void minE(T& a, const T& b) { a = min(a, b); } const int MAXN = 100 * 1000 + 1; const int INF = 1000 * 1000 * 1000 + 1; int n; int w1[MAXN]; int w2[MAXN]; int h1[MAXN]; int h2[MAXN]; int w1Min[MAXN]; int w2Max[MAXN]; int h1Min[MAXN]; int h2Max[MAXN]; int main() { ios_base::sync_with_stdio(0); int z; cin >> z; while(z--) { cin >> n; REP (i, n) cin >> w1[i] >> w2[i] >> h1[i] >> h2[i]; w1Min[n] = h1Min[n] = INF; w2Max[n] = h2Max[n] = -INF; for (int i = n - 1; i >= 0; i--) { w1Min[i] = min(w1[i], w1Min[i + 1]); h1Min[i] = min(h1[i], h1Min[i + 1]); w2Max[i] = max(w2[i], w2Max[i + 1]); h2Max[i] = max(h2[i], h2Max[i + 1]); } bool found = 0; int w1MinLeft = INF; int h1MinLeft = INF; int w2MaxLeft = -INF; int h2MaxLeft = -INF; REP (i, n) { bool foundHere = 1; if (w1[i] > min(w1MinLeft, w1Min[i + 1])) foundHere = 0; if (h1[i] > min(h1MinLeft, h1Min[i + 1])) foundHere = 0; if (w2[i] < max(w2MaxLeft, w2Max[i + 1])) foundHere = 0; if (h2[i] < max(h2MaxLeft, h2Max[i + 1])) foundHere = 0; if (foundHere) { debug cout << "found " << i << endl; debug cout << "w1[i] " << w1[i] << " w1MinLeft " << w1MinLeft << endl; found = 1; } minE(w1MinLeft, w1[i]); minE(h1MinLeft, h1[i]); maxE(w2MaxLeft, w2[i]); maxE(h2MaxLeft, h2[i]); } if (found) cout << "TAK" << endl; else cout << "NIE" << endl; } return 0; } |