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
// Parking.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h> 

using namespace std;

class samochod
{
public:
	int wysokosc;
	pair <int, int> xpocz, xkon; // poczatkowy i koncowy zakres na osi x zajmowany przez samochod

	samochod(int x1, int x2, int wys)
		{xpocz.first = min (x1,x2); xpocz.second = max(x1,x2); wysokosc = wys;}

	void przesuniecie(int x1, int x2)
		{xkon.first = min (x1,x2); xkon.second = max(x1,x2);}

};

bool sprawdz(const vector<samochod> & samochody, int wysokosc)
{
	for (int ii=0; ii < samochody.size(); ii++)
	{
		for (int jj = ii+1; jj < samochody.size(); jj++)
		{
			if(samochody[jj].xkon.first < samochody[ii].xkon.second && 
				samochody[ii].wysokosc + samochody[jj].wysokosc > wysokosc)
				return false;
		}
	}
	return true;
}

		

int main()
{
	int ile_testow, ile_sam, wysokosc; // wysokosc parkingu
	cin >> ile_testow;

	for (int t=0; t<ile_testow; t++)
	{
		cin >> ile_sam >> wysokosc;
		vector<samochod> samochody;
		for (int ii=0; ii < ile_sam; ii++) // wczytanie polozen poczatkowych samochodow
		{
			int x1,x2,y1,y2;
			cin >> x1 >> y1 >> x2 >> y2;
			samochody.push_back(samochod(x1, x2, abs(y2-y1)));
		}
		for (int ii=0; ii < ile_sam; ii++) // wczytanie polozen koncowych samochodow
		{
			int x1,x2,y1,y2;
			cin >> x1 >> y1 >> x2 >> y2;
			samochody[ii].przesuniecie(x1, x2);
			assert(abs(y2-y1) == samochody[ii].wysokosc);
		}

		sort(samochody.begin(), samochody.end(), [](samochod s1, samochod s2){return s1.xpocz.first < s2.xpocz.first;});

		bool wynik = sprawdz(samochody, wysokosc);

		if (wynik == true)
			cout << "TAK" <<endl;
		else
			cout << "NIE" <<endl;

	}

	return 0;
}