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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

struct Prostokat {
	int u, x1, x2, y1, y2;
	void wypisz() {
		printf("%d %d %d %d\n", x1, x2, y1, y2);
	}
} P[2][100000];

bool operator< (Prostokat a, Prostokat b) {
	if (a.x1 == b.x1) {
		if (a.x2 == b.x2) {
			if (a.y1 == b.y1) {
				return a.y2 > b.y2;
			} else {
				return a.y1 < b.y1;
			}
		} else {
			return a.x2 > b.x2;
		}
	} else {
		return a.x1 < b.x1;
	}
}

bool operator== (Prostokat a, Prostokat b) {
	return a.x1 == b.x1 && a.x2 == b.x2 && a.y1 == b.y1 && a.y2 == b.y2;
}

bool laczaSie(Prostokat a, Prostokat b) {
	return !(b.x2 <= a.x1 || a.x2 <= b.x1 || b.y2 <= a.y1 || a.y2 <= b.y1);
}

bool porownajLeksykograficznie(Prostokat a, Prostokat b) {
	if (a.x1 == b.x1) {
		if (a.x2 == b.x2) {
			if (a.y1 == b.y1) {
				return a.y2 < b.y2;
			} else {
				return a.y1 < b.y1;
			}
		} else {
			return a.x2 < b.x2;
		}
	} else {
		return a.x1 < b.x1;
	}
}

int main() {
	int k = 1, m, n, p = 0, z;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		P[p][i].u = 0;
		scanf("%d %d %d %d", &P[p][i].x1, &P[p][i].x2, &P[p][i].y1, &P[p][i].y2);
		if (P[p][i].x2 < P[p][i].x1) swap(P[p][i].x1, P[p][i].x2);
		if (P[p][i].y2 < P[p][i].y1) swap(P[p][i].y1, P[p][i].y2);
	}
	sort(P[p], P[p] + n);
	while (true) {
		z = 0;
		if (k) {
			for (int i = 0; i < n; ++i) {
				if (P[p][i].u) continue;
				for (int j = i + 1; j < n && P[p][j].x1 < P[p][i].x2; ++j) {
					if (P[p][j].u) continue;
					if (laczaSie(P[p][i], P[p][j])) {
						P[p][i].x1 = min(P[p][i].x1, P[p][j].x1);
						P[p][i].x2 = max(P[p][i].x2, P[p][j].x2);
						P[p][i].y1 = min(P[p][i].y1, P[p][j].y1);
						P[p][i].y2 = max(P[p][i].y2, P[p][j].y2);
						P[p][j].u = 1;
						if (!z) {
							k = i <= n - j - 1;
						}
						z = 1;
					}
				}
			}
		} else {
			for (int i = n - 1; i >= 0; --i) {
				if (P[p][i].u) continue;
				m = i;
				for (int j = i - 1; j >= 0 && P[p][j].x2 > P[p][i].x1; --j) {
					if (P[p][j].u) continue;
					if (laczaSie(P[p][j], P[p][i])) {
						P[p][i].x1 = min(P[p][j].x1, P[p][i].x1);
						P[p][i].x2 = max(P[p][j].x2, P[p][i].x2);
						P[p][i].y1 = min(P[p][j].y1, P[p][i].y1);
						P[p][i].y2 = max(P[p][j].y2, P[p][i].y2);
						P[p][j].u = 1;
						m = j;
						if (!z) {
							k = j <= n - i - 1;
						}
						z = 1;
					}
				}
				if (m < i) {
					P[p][m] = P[p][i];
					P[p][i].u = 1;
				}
			}
		}
		if (!z) break;
		m = 0;
		for (int i = 0; i < n; ++i) {
			if (P[p][i].u) continue;
			P[!p][m++] = P[p][i];
		}
		p = !p;
		n = m;
	}
	while (true) {
		z = 0;
		for (int i = 0; i < n; ++i) {
			if (P[p][i].u) continue;
			for (int j = i + 1; j < n && P[p][j].x1 < P[p][i].x2; ++j) {
				if (P[p][j].u) continue;
				if (laczaSie(P[p][i], P[p][j])) {
					P[p][i].x1 = min(P[p][i].x1, P[p][j].x1);
					P[p][i].x2 = max(P[p][i].x2, P[p][j].x2);
					P[p][i].y1 = min(P[p][i].y1, P[p][j].y1);
					P[p][i].y2 = max(P[p][i].y2, P[p][j].y2);
					P[p][j].u = 1;
					z = 1;
				}
			}
		}
		if (!z) break;
		m = 0;
		for (int i = 0; i < n; ++i) {
			if (P[p][i].u) continue;
			P[!p][m++] = P[p][i];
		}
		p = !p;
		n = m;
	}
	sort(P[p], P[p] + n, porownajLeksykograficznie);
	printf("%d\n", n);
	P[p][0].wypisz();
	for (int i = 1; i < n; ++i) {
		if (P[p][i - 1] == P[p][i]) continue;
		P[p][i].wypisz();
	}
	return 0;
}