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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

//#define _DEBUG
#define PRZYBLIZENIE 1300

#define REP(x, n) for(int x = 0; x < (n); ++x)

using namespace std;

// FAU skopiowane z "Algorytmiki praktycznej w konkursach informatycznych" P. Stanczyka
struct FAU{
int *p, *w;
FAU(int n) : p(new int[n]), w(new int[n]) {
REP(x, n) p[x] = w[x] = -1;
}

/*~FAU() {
delete[]p;
delete[]w;
}*/

int Find(int x) {
return (p[x] < 0) ? x : p[x] = Find(p[x]);
}

void Union(int x, int y) {
if ((x = Find(x)) == (y = Find(y))) return;
if (w[x] > w[y]) p[y] = x;
else p[x] = y;
if (w[x] == w[y]) w[y]++;
}
};

int main() {
int n;
scanf("%d", &n);
int *x_min = new int[n+5];
int *x_max = new int[n+5];
int *y_min = new int[n+5];
int *y_max = new int[n+5];
for (int i=1;i<=n;i++) {
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
x_min[i]=x1;
x_max[i]=x2;
y_min[i]=y1;
y_max[i]=y2;
}
FAU zbiory_x = FAU(n+1);
vector<pair<int, int> > os_x;
for (int i=1;i<=n;i++) {
os_x.push_back(make_pair(x_min[i], i));
os_x.push_back(make_pair(x_max[i], -i));
}
sort(os_x.begin(), os_x.end());
# ifdef _DEBUG
printf("Os X: "); for (int i=0;i<os_x.size();i++) printf("(%d, %d) ", os_x[i].first, os_x[i].second); printf("\n");
# endif
vector<pair<int, int> > os_y;
for (int i=1;i<=n;i++) {
os_y.push_back(make_pair(y_min[i], i));
os_y.push_back(make_pair(y_max[i], -i));
}
sort(os_y.begin(), os_y.end());
# ifdef _DEBUG
printf("Os Y: "); for (int i=0;i<os_y.size();i++) printf("(%d, %d) ", os_y[i].first, os_y[i].second); printf("\n");
# endif
int *last_kombi = new int[n+5];
int *ile_kombi = new int[n+5];
for (int i=0;i<=n;i++) last_kombi[i] = ile_kombi[i] = 0;


FAU zbiory_result = FAU(n+1);
for (int i=1;i<=n;i++) zbiory_result.Union(i-1,i);
FAU zbory_kombi = FAU(n+1);
for (int q=0;q<PRZYBLIZENIE;q++) {
FAU zbiory_kombi = FAU(n+1);
// Po X-ie
for (int i=0;i<os_x.size();i++) {
if (os_x[i].second > 0) {
if (ile_kombi[zbiory_result.Find(os_x[i].second)]>0) {zbiory_kombi.Union(os_x[i].second, last_kombi[zbiory_result.Find(os_x[i].second)]);}
ile_kombi[zbiory_result.Find(os_x[i].second)]++; last_kombi[zbiory_result.Find(os_x[i].second)]=os_x[i].second;}
else {ile_kombi[zbiory_result.Find(-os_x[i].second)] --;}
}

zbiory_result = zbiory_kombi;
zbiory_kombi = FAU(n+1);

for (int i=0;i<=n;i++) last_kombi[i] = ile_kombi[i] = 0;
// Po Y-greku
for (int i=0;i<os_y.size();i++) {
if (os_y[i].second > 0) {
if (ile_kombi[zbiory_result.Find(os_y[i].second)]>0) {zbiory_kombi.Union(os_y[i].second, last_kombi[zbiory_result.Find(os_y[i].second)]);}
ile_kombi[zbiory_result.Find(os_y[i].second)]++; last_kombi[zbiory_result.Find(os_y[i].second)]=os_y[i].second;}
else {ile_kombi[zbiory_result.Find(-os_y[i].second)] --;}
}

zbiory_result = zbiory_kombi;
zbiory_kombi = FAU(n+1);

}

// Kombi
FAU zbiory_kombi = FAU(n+1);
for (int i=0;i<os_x.size();i++) {
if (os_x[i].second > 0) {
if (ile_kombi[zbiory_result.Find(os_x[i].second)]>0) {zbiory_kombi.Union(os_x[i].second, last_kombi[zbiory_result.Find(os_x[i].second)]);}
ile_kombi[zbiory_result.Find(os_x[i].second)]++; last_kombi[zbiory_result.Find(os_x[i].second)]=os_x[i].second;}
else {ile_kombi[zbiory_result.Find(-os_x[i].second)] --;}
}


set<int> s;
int * x_min_result = new int[n+1];
int * x_max_result = new int[n+1];
int * y_min_result = new int[n+1];
int * y_max_result = new int[n+1];
for (int i=0;i<=n;i++) x_min_result[i] = y_min_result[i] = 1000100;
for (int i=0;i<=n;i++) x_max_result[i] = y_max_result[i] = -1;
for (int i=1;i<=n;i++) {
int el = zbiory_kombi.Find(i);
s.insert(el); 
x_min_result[el] = min(x_min_result[el], x_min[i]);
y_min_result[el] = min(y_min_result[el], y_min[i]);
y_max_result[el] = max(y_max_result[el], y_max[i]);
x_max_result[el] = max(x_max_result[el], x_max[i]);
}



vector<pair<pair<int, int>, pair<int, int> > > result;
for (set<int>::iterator it = s.begin();it!=s.end();it++) {
result.push_back(make_pair(make_pair(x_min_result[*it], x_max_result[*it]), make_pair(y_min_result[*it], y_max_result[*it])));
}
sort(result.begin(), result.end());
printf("%lu\n", s.size());
for (int i=0;i<result.size();i++) printf("%d %d %d %d\n", result[i].first.first, result[i].first.second, result[i].second.first, result[i].second.second);
return 0;
}