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

#include <iostream>
#include <list>
#include <tuple>

using namespace std;

class plemie
{
public:
	int x1, x2, y1, y2;
	plemie (int x_a, int x_b, int y_a, int y_b)
	{
		x1 = min(x_a, x_b); x2 = max(x_a, x_b);
		y1 = min(y_a, y_b); y2 = max(y_a, y_b);
	}
	void przylacz (const plemie & other)
	{
		x1 = min(x1, other.x1); x2 = max(x2, other.x2);
		y1 = min(y1, other.y1); y2 = max(y2, other.y2);
	}
	bool sprawdz_przeciecie (const plemie & other)
	{
		if(x2 <= other.x1 || x1 >= other.x2 || y2 <= other.y1 || y1 >= other.y2)
			return false;
		else return true;
	}
	bool operator < (const plemie & other)
	{ return tie(x1,x2,y1,y2) < tie(other.x1, other.x2, other.y1, other.y2);}
};


void dodaj_plemie (plemie nowe_plemie, list<plemie> & plemiona)
{
	bool byla_zmiana = true;
	while(byla_zmiana)
	{
		byla_zmiana = false;
		list<plemie>::iterator it = plemiona.begin();
		while ( it != plemiona.end())
		{
			if (nowe_plemie.sprawdz_przeciecie(*it) == true)
			{
				byla_zmiana = true;
				nowe_plemie.przylacz((*it));
				it = plemiona.erase(it);
			}
			else ++it;
		}
	}
	plemiona.push_front(nowe_plemie);
}

int main()
{
	int ile_plemion;
	cin >> ile_plemion;

	list<plemie> plemiona; // kazde plemie (el. wektora) opisane jest 4 liczbami: x_min, x_max, y_min, y_max - granice zajmowanego obszaru

	for (int ii=0; ii< ile_plemion; ii++)
	{
		int x1, x2, y1, y2;
		cin >> x1 >> x2 >> y1 >> y2;
		plemie nowe_plemie = plemie(x1, x2, y1, y2);
		dodaj_plemie(nowe_plemie, plemiona);
	}
	
	plemiona.sort();

	cout << plemiona.size() << endl;

	for (list<plemie>::iterator it = plemiona.begin(); it != plemiona.end(); ++it)
		cout << it->x1 << " " << it->x2 << " " << it->y1 << " " << it->y2 << endl;

	return 0;
}