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
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;

int main() {
	
	int k;
	scanf("%d",&k);
	
	for (int ik=0; ik<k; ik++)
	{
		int n, w;
		scanf("%d%d",&n,&w);
		
		int x1p[n], x2p[n], y1p[n], y2p[n];
		int x1k[n], x2k[n], y1k[n], y2k[n];
		vector <pair<int,int> > v;
		
		for (int i=0; i<n; i++)
		{
			scanf("%d%d%d%d",&x1p[i],&y1p[i],&x2p[i],&y2p[i]);
			if (x1p[i] > x2p[i])
			{
				int pom = x1p[i];
				x1p[i] = x2p[i];
				x2p[i] = pom;
			}
			
			if (y1p[i] > y2p[i])
			{
				int pom = y1p[i];
				y1p[i] = y2p[i];
				y2p[i] = pom;
			}
			
			pair<int,int> p;
			p.first = - (y2p[i] - y1p[i]); //minus zeby posortowalo malejaco
			//printf("Wys: %d\n",p.first);
			p.second = i;
			v.push_back(p);
		}
		
		for (int i=0; i<n; i++)
		{
			scanf("%d%d%d%d",&x1k[i],&y1k[i],&x2k[i],&y2k[i]);
			if (x1k[i] > x2k[i])
			{
				int pom = x1k[i];
				x1k[i] = x2k[i];
				x2k[i] = pom;
			}
		}
		
		sort(v.begin(),v.end());
		
		bool isOK = true;
		for (int i=0; i<n; i++)
		{
			int j = i+1;
			while (j < n && -v[i].first - v[j].first > w) //minusy, bo... patrz wyzej
			{
				if ((x1p[v[i].second] >= x2p[v[j].second] && x1k[v[j].second] >= x2k[v[i].second]) ||
				(x1p[v[j].second] >= x2p[v[i].second] && x1k[v[i].second] >= x2k[v[j].second]))//sprawdzic, tu moze byc blad
				{
					isOK = false;
					break;
				}
				j++;
			}
			
			if (j == i+1 || !isOK) break; //dwa kolejne maja mniejsza sume wysokosci niz w
		}
		
		if (isOK)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}