#include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstring> #include <iostream> #include <algorithm> #include <set> #define MAXN 50007 #define czapa 65536 #define INF #define PB push_back #define MP make_pair #define ST first #define ND second #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(a,b,c) for(int a=b;a<=(c);a++) #define FORD(a,b,c) for (int a=b;a>=(c);a--) #define VAR(v,n) __typeof(n) v=(n) #define ALL(c) c.begin(),c.end() #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++) using namespace std; typedef long long LL; typedef pair<int,int> PII; bool mozna; int wys_park,testy,n,x_1,y_1,x_2,y_2; int gdzie[MAXN],wys[MAXN]; int drzewo[2*czapa]; PII pocz[MAXN],kon[MAXN]; void insert(int poz, int v) { poz += czapa; drzewo[poz] = v; while (poz != 1) { poz /= 2; drzewo[poz] = max(drzewo[poz*2],drzewo[poz*2+1]); } } int query(int p) { int l = czapa; p += czapa; int res = max(drzewo[l],drzewo[p]); while (l/2 != p/2) { if (!(l&1)) res = max(res,drzewo[l+1]); if (p&1) res = max(res,drzewo[p-1]); l /= 2; p /= 2; } return res; } int main(){ scanf("%d",&testy); while (testy--) { mozna = true; scanf("%d%d",&n,&wys_park); REP(i,n) { scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2); wys[i] = abs(y_1-y_2); pocz[i] = MP(min(x_1,x_2),i); } REP(i,n) { scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2); kon[i] = MP(min(x_1,x_2),i); } sort(pocz,pocz+n); sort(kon,kon+n); REP(i,n) gdzie[pocz[i].ND] = i; REP(i,n) insert(i,wys[pocz[i].ND]); REP(i,n) { insert(gdzie[kon[i].ND],0); if (query(gdzie[kon[i].ND]) + wys[kon[i].ND] > wys_park) mozna = false; } puts(mozna ? "TAK" : "NIE"); } 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 77 78 79 80 81 82 83 84 85 86 | #include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstring> #include <iostream> #include <algorithm> #include <set> #define MAXN 50007 #define czapa 65536 #define INF #define PB push_back #define MP make_pair #define ST first #define ND second #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(a,b,c) for(int a=b;a<=(c);a++) #define FORD(a,b,c) for (int a=b;a>=(c);a--) #define VAR(v,n) __typeof(n) v=(n) #define ALL(c) c.begin(),c.end() #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++) using namespace std; typedef long long LL; typedef pair<int,int> PII; bool mozna; int wys_park,testy,n,x_1,y_1,x_2,y_2; int gdzie[MAXN],wys[MAXN]; int drzewo[2*czapa]; PII pocz[MAXN],kon[MAXN]; void insert(int poz, int v) { poz += czapa; drzewo[poz] = v; while (poz != 1) { poz /= 2; drzewo[poz] = max(drzewo[poz*2],drzewo[poz*2+1]); } } int query(int p) { int l = czapa; p += czapa; int res = max(drzewo[l],drzewo[p]); while (l/2 != p/2) { if (!(l&1)) res = max(res,drzewo[l+1]); if (p&1) res = max(res,drzewo[p-1]); l /= 2; p /= 2; } return res; } int main(){ scanf("%d",&testy); while (testy--) { mozna = true; scanf("%d%d",&n,&wys_park); REP(i,n) { scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2); wys[i] = abs(y_1-y_2); pocz[i] = MP(min(x_1,x_2),i); } REP(i,n) { scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2); kon[i] = MP(min(x_1,x_2),i); } sort(pocz,pocz+n); sort(kon,kon+n); REP(i,n) gdzie[pocz[i].ND] = i; REP(i,n) insert(i,wys[pocz[i].ND]); REP(i,n) { insert(gdzie[kon[i].ND],0); if (query(gdzie[kon[i].ND]) + wys[kon[i].ND] > wys_park) mozna = false; } puts(mozna ? "TAK" : "NIE"); } return 0; } |