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

int n;
int w;

//#define ASSERT

#define ISORT(a,b) if(a>b) { int tmp=a; a=b; b=tmp; }

struct Car {
	int ix1,ix2, iy1,iy2;
	int ox1,ox2, oy1,oy2;
	int height;
	int i;
	int pos;
	
	void readIn(int i) {
		this->i=i;
		this->pos=-1;
		scanf("%d %d %d %d",&ix1, &iy1, &ix2, &iy2);
		ISORT(ix1,ix2);
		ISORT(iy1,iy2);
		
#ifdef ASSERT
		if(ix1>=ix2) printf("FATAL IN\n");
#endif
		// TODO: Poprawiac wpisy, aby x1<x2 i y1<y2
		this->height=iy2-iy1;
	}
	void readOut(int i) {
		// assert this->==i;
		scanf("%d %d %d %d",&ox1, &oy1, &ox2, &oy2);
		ISORT(ox1,ox2);
		ISORT(oy1,oy2);
#ifdef ASSERT
		if(ox1>=ox2) printf("FATAL OUT\n");
		if( (iy2-iy1) != (oy2-oy1) ) printf("FATAL HEIGHT\n");
		if( (ix2-ix1) != (ox2-ox1) ) printf("FATAL WIDTH\n");
#endif
		// TODO: Poprawiac wpisy, aby x1<x2 i y1<y2
	}
};

Car* data;
Car** in;
Car** out;

#define SC(x)   (*((Car**)x))

int carSortIn(const void* v1, const void *v2) { return SC(v1)->ix2 - SC(v2)->ix2; }
int carSortOut(const void* v1, const void *v2) { return SC(v1)->ox2 - SC(v2)->ox2; }

void logState(const char* msg, Car** state) {
#ifdef DEBUG
	printf("%s [%d]:\n",msg,n);
	for(int i=0;i<n;++i) printf("  % 3d @%d (%d,%d-%d,%d)+(%d,%d-%d,%d)\n",state[i]->i+1,state[i]->pos, state[i]->ix1,state[i]->iy1,state[i]->ix2,state[i]->iy2, state[i]->ox1,state[i]->oy1,state[i]->ox2,state[i]->oy2 );
#endif
}

/** Przetwarza dane */
bool process() {
	for(int i=0;i<n;++i) {
		Car* c=out[i];	// po kolei kazdy samochów według koncowego ułożenia
		int left=w - c->height;	// tyle jest wolnego miejsca
		while(c->pos>i) {	// idziemy w lewo
			Car* sw=in[c->pos-1];	// do sprawdzenia
			if( sw->height>left) {
#ifdef DEBUG
				printf("Invalid state at %d (%d !! %d)\n",c->pos,c->i+1, sw->i+1);
				logState("State", in);
#endif
				return false;	// samochod sie nie przecisnie
			}
			sw->pos++;	// aktualizacja pozycji
			in[sw->pos]=sw;		// aktualizacja w tablicy
			c->pos--;
		}
		in[c->pos]=c;	// aktualizacja w tablicy
	}

	return true;
}

int main() {
	data=(Car*)malloc(sizeof(Car)*   50000);
	
	in=(Car**)malloc(sizeof(Car*)*   50000);
	out=(Car**)malloc(sizeof(Car*)*  50000);
	
	int tests;
	scanf("%d",&tests);
	// iteracja po testach
	for(int test=0;test<tests;++test) {
		// odczyt danych jednego testu
		scanf("%d %d",&n,&w);
		for(int i=0;i<n;++i) {
			in[i]=&data[i];
			in[i]->readIn(i);
		}
		for(int i=0;i<n;++i) {
			out[i]=&data[i];
			out[i]->readOut(i);
		}
		logState("Readed",in);
		
		qsort(in,n,sizeof(Car*),carSortIn);
		qsort(out,n,sizeof(Car*),carSortOut);
		for(int i=0;i<n;++i) in[i]->pos=i;
		logState("Input sorted",in);
		logState("Output sorted",out);
		printf("%s\n",process()?"TAK":"NIE");
	}
	
	
	return 0;
}