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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <cstdlib>
#include <map>
#include <list>
using namespace std;
typedef  pair<int,int> p;

int main(){
	map<int,vector<int> > m;
	multiset<pair<p,int>> x1,x2;
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);

		vector<int> t;
		t.push_back(a);
		t.push_back(b);
		t.push_back(c);
		t.push_back(d);
		m.insert(make_pair(i,t));
		x1.insert(make_pair(make_pair(a,1),i));
		x2.insert(make_pair(make_pair(b,0),i));

	}

		multiset<pair<p,int>> sw;
		sw.insert(x1.begin(),x1.end());
		sw.insert(x2.begin(),x2.end());
		set<p> active;//y

		int c=0;
		auto it=sw.begin();
		while(it!=sw.end())
		{
			//spr czy koniec
			if(!(it->first.second)) {
				active.erase(make_pair(m[it->second][2],it->second));active.erase(make_pair(m[it->second][3],it->second));
			//	//cout<<"koniec"<<it->second<<endl;

				p tof1=make_pair(m[it->second][2],it->second);
				p tof2=make_pair(m[it->second][3],it->second);
				set<p>::iterator t1=active.lower_bound(tof1);
				set<p>::iterator  t2=active.lower_bound(tof2);

				if( t1==t2)//nie przecina ale moze sie zawierac
				{

					if(!active.empty() &&m[(t1)->second][2]<=tof1.first &&m[(t1)->second][3]>=tof2.first)
					{	//cout<<"zawiera"<<it->second<<t1->second;
					vector<int> t;
					t.push_back(min(m[t1->second][0],m[tof1.second][0]));
					t.push_back(max(m[t1->second][1],m[tof1.second][1]));
					t.push_back(min(m[t1->second][2],m[tof1.second][2]));
					t.push_back(max(m[t1->second][3],m[tof1.second][3]));
					sw.erase(make_pair(make_pair(m[it->second][1],0),it->second));
					sw.erase(make_pair(make_pair(m[it->second][0],1),it->second));
					sw.erase(make_pair(make_pair(m[t1->second][1],0),t1->second));
					sw.erase(make_pair(make_pair(m[t1->second][0],1),t1->second));
					m[tof1.second].clear();
					m[(t1->second)].clear();

					m[tof1.second]=t;


					sw.insert(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
					sw.insert(make_pair(make_pair(m[tof1.second][1],0),tof1.second));
					active.erase(make_pair(m[t1->second][2],t1->second));
					active.erase(make_pair(m[t1->second][3],t1->second));
					it=sw.find(make_pair(make_pair(m[tof1.second][0],1),tof1.second));

					}

					else
			{

					++it;
					//cout<<"poczatek nie przecina";
			}

				}else{
					//cout<<"przecinaja sie";

					vector<int> t;
					t.push_back(min(m[t1->second][0],m[tof1.second][0]));
					t.push_back(max(m[t1->second][1],m[tof1.second][1]));
					t.push_back(min(m[t1->second][2],m[tof1.second][2]));
					t.push_back(max(m[t1->second][3],m[tof1.second][3]));
					sw.erase(make_pair(make_pair(m[it->second][1],0),it->second));
									sw.erase(make_pair(make_pair(m[it->second][0],1),it->second));
									sw.erase(make_pair(make_pair(m[t1->second][1],0),t1->second));
									sw.erase(make_pair(make_pair(m[t1->second][0],1),t1->second));
									m[tof1.second].clear();
									m[(t1->second)].clear();

									m[tof1.second]=t;


									sw.insert(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
									sw.insert(make_pair(make_pair(m[tof1.second][1],0),tof1.second));
									active.erase(make_pair(m[t1->second][2],t1->second));
									active.erase(make_pair(m[t1->second][3],t1->second));
									it=sw.find(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
				}
		}
			//w przeciwnym razie poczatek
			else
			{
				p tof1=make_pair(m[it->second][2],it->second);
				p tof2=make_pair(m[it->second][3],it->second);
				set<p>::iterator t1=active.lower_bound(tof1);
				set<p>::iterator  t2=active.lower_bound(tof2);

				if( t1==t2)//nie przecina ale moze sie zawierac
				{

					if(!active.empty() &&m[(t1)->second][2]<=tof1.first &&m[(t1)->second][3]>=tof2.first)
					{	//cout<<"zawiera"<<it->second<<t1->second;
					vector<int> t;
					t.push_back(min(m[t1->second][0],m[tof1.second][0]));
					t.push_back(max(m[t1->second][1],m[tof1.second][1]));
					t.push_back(min(m[t1->second][2],m[tof1.second][2]));
					t.push_back(max(m[t1->second][3],m[tof1.second][3]));
					sw.erase(make_pair(make_pair(m[it->second][1],0),it->second));
					sw.erase(make_pair(make_pair(m[it->second][0],1),it->second));
					sw.erase(make_pair(make_pair(m[t1->second][1],0),t1->second));
					sw.erase(make_pair(make_pair(m[t1->second][0],1),t1->second));
					m[tof1.second].clear();
					m[(t1->second)].clear();

					m[tof1.second]=t;


					sw.insert(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
					sw.insert(make_pair(make_pair(m[tof1.second][1],0),tof1.second));
					active.erase(make_pair(m[t1->second][2],t1->second));
					active.erase(make_pair(m[t1->second][3],t1->second));
					it=sw.find(make_pair(make_pair(m[tof1.second][0],1),tof1.second));

					}

					else
			{
					active.insert(tof1);
					active.insert(tof2);
					++it;
					//cout<<"poczatek nie przecina";
			}

				}else{
					//cout<<"przecinaja sie";

					vector<int> t;
					t.push_back(min(m[t1->second][0],m[tof1.second][0]));
					t.push_back(max(m[t1->second][1],m[tof1.second][1]));
					t.push_back(min(m[t1->second][2],m[tof1.second][2]));
					t.push_back(max(m[t1->second][3],m[tof1.second][3]));
					sw.erase(make_pair(make_pair(m[it->second][1],0),it->second));
									sw.erase(make_pair(make_pair(m[it->second][0],1),it->second));
									sw.erase(make_pair(make_pair(m[t1->second][1],0),t1->second));
									sw.erase(make_pair(make_pair(m[t1->second][0],1),t1->second));
									m[tof1.second].clear();
									m[(t1->second)].clear();

									m[tof1.second]=t;


									sw.insert(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
									sw.insert(make_pair(make_pair(m[tof1.second][1],0),tof1.second));
									active.erase(make_pair(m[t1->second][2],t1->second));
									active.erase(make_pair(m[t1->second][3],t1->second));
									it=sw.find(make_pair(make_pair(m[tof1.second][0],1),tof1.second));
				}
			}

		}


		vector<vector<int>> pp;
for(auto it=m.begin();it!=m.end();++it){
	if(!(it->second).empty())
		{pp.push_back(it->second);c++; m.erase(it);}}
printf("%d\n",c);
sort(pp.begin(),pp.end(),[](vector<int> a, vector<int> b){
	return (a[0]<b[0]) || (a[0]==b[0] &&a[1]<b[1]) ||(a[0]==b[0] &&a[1]==b[1] && a[2]<b[2])
		|| (a[0]==b[0] &&a[1]==b[1] && a[2]==b[2] && a[3]<b[3]);});
for(auto vv:pp)
{for (auto i:vv) printf("%d ",i); printf("\n");}
	return 0;
}