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

typedef pair<int, bool> pib;

const int nmax = 1e5+10;

struct {
	int x1, x2, y1, y2;

	inline int getX(bool b) { return b ? x1 : x2; }
	inline int getY(bool b) { return b ? y1 : y2; }
} tribe[nmax];

struct xordercmp { 
	bool operator() (const pib& lhs, const pib& rhs) {
		int xlhs = tribe[lhs.first].getX(lhs.second);
		int xrhs = tribe[rhs.first].getX(rhs.second);
		if (xlhs != xrhs) return xlhs < xrhs;
		int ylhs = tribe[lhs.first].getY(lhs.second);
		int yrhs = tribe[rhs.first].getY(rhs.second);
		if (ylhs != yrhs) return ylhs < yrhs;
		return lhs < rhs;
	}
};

struct yordercmp {
	bool operator() (const pib& lhs, const pib& rhs) {
		int ylhs = tribe[lhs.first].getY(lhs.second);
		int yrhs = tribe[rhs.first].getY(rhs.second);
		if (ylhs != yrhs) return ylhs < yrhs;
		int xlhs = tribe[lhs.first].getX(lhs.second);
		int xrhs = tribe[rhs.first].getX(rhs.second);
		if (xlhs != xrhs) return xlhs < xrhs;
		return lhs < rhs;
	}
};

int n;
typedef set<pib, xordercmp> set_pib_x;
typedef set<pib, yordercmp> set_pib_y;
set_pib_x xorder;
set_pib_y yorder;

struct {
	vector<int> xA, xB, yA, yB;
	vector<int> order;
	int counter;

	void push(int tid_xa, int tid_xb, int tid_ya, int tid_yb) {
		order.push_back(counter++);
		xA.push_back(tribe[tid_xa].x1);
		xB.push_back(tribe[tid_xb].x2);
		yA.push_back(tribe[tid_ya].y1);
		yB.push_back(tribe[tid_yb].y2);
	}
} ans;

bool anscmp(const int lhs, const int rhs) {
	if (ans.xA[lhs] != ans.xA[rhs]) return ans.xA[lhs] < ans.xA[rhs];
	if (ans.xB[lhs] != ans.xB[rhs]) return ans.xB[lhs] < ans.xB[rhs];
	if (ans.yA[lhs] != ans.yA[rhs]) return ans.yA[lhs] < ans.yA[rhs];
	return ans.yB[lhs] < ans.yB[rhs];
}

void baseCase() {
	cout << "1\n";
	cout << tribe[1].x1 << ' ' << tribe[1].x2 << ' ' << tribe[1].y1 << ' ' << tribe[1].y2 << '\n';
}

void debug() {
	for (auto x : xorder) {
		cerr << x.first << (x.second ? "." : "") << " ";
	} cerr << endl;

	for (auto x : yorder) {
		cerr << x.first << (x.second ? "." : "") << " ";
	} cerr << endl;
}

void solve(set_pib_x currentX, set_pib_y currentY) {
	// cerr << "solve " << currentX.size() << " " << currentY.size() << "\n";
	// cerr << "can split on x?\n";
	int d = 0;
	auto split = currentX.end();
	for (auto it = currentX.begin(); it != currentX.end(); it++) {
		if (it->second) d++; else d--;
		if (d == 0) { split = it; break; }
	}
	split++;
	if (split != currentX.end()) {
		// cerr << split->first << "\n";
		set_pib_x nextX; set_pib_y nextY;
		while (split != currentX.end()) {
			nextX.insert(*split);
			nextY.insert(*split);
			currentY.erase(*split);
			split = currentX.erase(split);
		}
		solve(currentX, currentY);
		solve(nextX, nextY);
	} else {
		// cerr << "can split on y?\n";
		d = 0;
		split = currentY.end();
		for (auto it = currentY.begin(); it != currentY.end(); it++) {
			if (it->second) d++; else d--;
			if (d == 0) { split = it; break; }
		}
		split++;
		if (split != currentY.end()) {
			// cerr << split->first << "\n";
			set_pib_x nextX; set_pib_y nextY;
			while (split != currentY.end()) {
				nextY.insert(*split);
				nextX.insert(*split);
				currentX.erase(*split);
				split = currentY.erase(split);
			}
			solve(currentX, currentY);
			solve(nextX, nextY);
		}
		else {
			// cerr << "no split!\n";
			ans.push(currentX.begin()->first, currentX.rbegin()->first, currentY.begin()->first, currentY.rbegin()->first);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> tribe[i].x1 >> tribe[i].x2 >> tribe[i].y1 >> tribe[i].y2;
		xorder.insert(make_pair(i, false)); xorder.insert(make_pair(i, true));
		yorder.insert(make_pair(i, false)); yorder.insert(make_pair(i, true));
	}

	if (n == 1) { baseCase(); return 0; }

	// debug();

	ans.counter = 0;
	solve(xorder, yorder);

	sort(ans.order.begin(), ans.order.end(), anscmp);

	cout << ans.xA.size() << "\n";
	for (int i = 0; i < ans.xA.size(); i++) {
		// cerr << ans.order[i] << "\n";
		int j = ans.order[i];
		cout << ans.xA[j] << " " << ans.xB[j] << " " << ans.yA[j] << " " << ans.yB[j] << "\n";
	}
	return 0;
}