#define debug if(0) // Grzegorz Guspiel #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<int(n);++i) #define SIZE(c) ((int)((c).size())) #define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) #define ALL(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define st first #define nd second typedef pair<int,int> PII; template<typename T> void maxE(T& a, const T& b) { a = max(a, b); } template<typename T> void minE(T& a, const T& b) { a = min(a, b); } template<typename T> ostream& operator<<(ostream& out, const vector<T>& t) { out << "["; FOREACH (i, t) out << *i << ", "; out << "]"; return out; } template<typename S, typename T> ostream& operator<<(ostream& out, const pair<S, T>& rhs) { out << "(" << rhs.st << "," << rhs.nd << ")"; return out; } typedef set<int>::iterator sit; struct Rect { int x1, y1, x2, y2; }; ostream& operator<<(ostream& out, const Rect& r) { out << "(" << r.x1 << "," << r.y1 << ")-(" << r.x2 << "," << r.y2 << ")"; return out; } bool cmpX1(const Rect& a, const Rect& b) { return a.x1 < b.x1; } Rect defaultRect() { Rect r; r.x1=r.x2=r.y1=r.y2=-1; return r; } vector<Rect> rects; struct SetCmp { bool operator()(int a, int b) { return rects[a].x2 < rects[b].x2; } }; struct Tree { set<int, SetCmp> d[2097157]; int t[2097157]; static const int s; SetCmp cmp; void improve(int& a, int b) { if (cmp(a, b)) a = b; } int added(int a) { return d[a].empty() ? 0 : *--d[a].end(); } int val(int a) { int r = added(a); improve(r, t[a]); return r; } void fix(int a) { t[a] = 0; improve(t[a], val(2 * a)); improve(t[a], val(2 * a + 1)); } void put(int rect, bool remove) { Rect& r = rects[rect]; int a = s + r.y1 + 1; int b = s + r.y2; a--; b++; assert(a >= s && a < 2 * s); assert(b >= s && b < 2 * s); debug cout << "put " << a << " " << b << endl; while (a / 2 != b / 2) { if (a + 1 != b) { if (a % 2 == 0) { debug cout << "put " << rects[rect] << a + 1 << endl; if (remove) d[a + 1].erase(rect); else d[a + 1].insert(rect); } if (b % 2 == 1) { debug cout << "put " << rects[rect] << b - 1 << endl; if (remove) d[b - 1].erase(rect); else d[b - 1].insert(rect); } } fix(a / 2); fix(b / 2); a /= 2; b /= 2; } while (a / 2) { fix(a / 2); a /= 2; } } void put(int rect) { put(rect, 0); } void remove(int rect) { put(rect, 1); } int get(Rect range) { int a = s + range.y1 + 1; int b = s + range.y2; a--; b++; assert(a >= s && a < 2 * s); assert(b >= s && b < 2 * s); debug cout << "ge0 " << range << " " << a << " " << b << endl; int r = 0; bool leftOk = 0; bool rightOk = 0; while (a / 2 != b / 2) { debug cout << "ge1 " << range << " " << a << " " << b << " r " << r << endl; if (a % 2 == 0) leftOk = 1; if (b % 2 == 1) rightOk = 1; if (a + 1 != b) { if (a % 2 == 0) improve(r, val(a + 1)); if (b % 2 == 1) improve(r, val(b - 1)); } if (leftOk) improve(r, added(a / 2)); if (rightOk) improve(r, added(b / 2)); a /= 2; b /= 2; } while (a / 2) { debug cout << "ge2 " << range << " " << a << " " << b << " r " << r << endl; improve(r, added(a / 2)); a /= 2; } debug cout << "ge3 " << range << " " << a << " " << b << " r " << r << endl; return r; } int getAny() { return val(1); } }; const int Tree::s = 1048576; Tree tree; void consume(int i, int j) { minE(rects[i].y1, rects[j].y1); maxE(rects[i].y2, rects[j].y2); maxE(rects[i].x2, rects[j].x2); minE(rects[i].x1, rects[j].x1); } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; REP (i, n) { Rect r; cin >> r.x1 >> r.x2 >> r.y1 >> r.y2; rects.pb(r); } sort(ALL(rects), cmpX1); rects.insert(rects.begin(), defaultRect()); vector<vector<int> > result; REP (i, SIZE(rects)) if (i) { while (true) { int ri = tree.get(rects[i]); Rect& me = rects[i]; Rect& r = rects[ri]; if (r.x2 > me.x1) { debug cout << me << " consumes " << r << endl; consume(i, ri); tree.remove(ri); continue; } break; } tree.put(i); } while (true) { int top = tree.getAny(); if (!top) break; tree.remove(top); Rect& r = rects[top]; vector<int> four; four.pb(r.x1); four.pb(r.x2); four.pb(r.y1); four.pb(r.y2); result.pb(four); } sort(ALL(result)); cout << SIZE(result) << endl; FOREACH (i, result) { FOREACH (j, *i) cout << *j << " "; cout << endl; } return 0; }
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 | #define debug if(0) // Grzegorz Guspiel #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<int(n);++i) #define SIZE(c) ((int)((c).size())) #define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i) #define ALL(v) (v).begin(), (v).end() #define pb push_back #define mp make_pair #define st first #define nd second typedef pair<int,int> PII; template<typename T> void maxE(T& a, const T& b) { a = max(a, b); } template<typename T> void minE(T& a, const T& b) { a = min(a, b); } template<typename T> ostream& operator<<(ostream& out, const vector<T>& t) { out << "["; FOREACH (i, t) out << *i << ", "; out << "]"; return out; } template<typename S, typename T> ostream& operator<<(ostream& out, const pair<S, T>& rhs) { out << "(" << rhs.st << "," << rhs.nd << ")"; return out; } typedef set<int>::iterator sit; struct Rect { int x1, y1, x2, y2; }; ostream& operator<<(ostream& out, const Rect& r) { out << "(" << r.x1 << "," << r.y1 << ")-(" << r.x2 << "," << r.y2 << ")"; return out; } bool cmpX1(const Rect& a, const Rect& b) { return a.x1 < b.x1; } Rect defaultRect() { Rect r; r.x1=r.x2=r.y1=r.y2=-1; return r; } vector<Rect> rects; struct SetCmp { bool operator()(int a, int b) { return rects[a].x2 < rects[b].x2; } }; struct Tree { set<int, SetCmp> d[2097157]; int t[2097157]; static const int s; SetCmp cmp; void improve(int& a, int b) { if (cmp(a, b)) a = b; } int added(int a) { return d[a].empty() ? 0 : *--d[a].end(); } int val(int a) { int r = added(a); improve(r, t[a]); return r; } void fix(int a) { t[a] = 0; improve(t[a], val(2 * a)); improve(t[a], val(2 * a + 1)); } void put(int rect, bool remove) { Rect& r = rects[rect]; int a = s + r.y1 + 1; int b = s + r.y2; a--; b++; assert(a >= s && a < 2 * s); assert(b >= s && b < 2 * s); debug cout << "put " << a << " " << b << endl; while (a / 2 != b / 2) { if (a + 1 != b) { if (a % 2 == 0) { debug cout << "put " << rects[rect] << a + 1 << endl; if (remove) d[a + 1].erase(rect); else d[a + 1].insert(rect); } if (b % 2 == 1) { debug cout << "put " << rects[rect] << b - 1 << endl; if (remove) d[b - 1].erase(rect); else d[b - 1].insert(rect); } } fix(a / 2); fix(b / 2); a /= 2; b /= 2; } while (a / 2) { fix(a / 2); a /= 2; } } void put(int rect) { put(rect, 0); } void remove(int rect) { put(rect, 1); } int get(Rect range) { int a = s + range.y1 + 1; int b = s + range.y2; a--; b++; assert(a >= s && a < 2 * s); assert(b >= s && b < 2 * s); debug cout << "ge0 " << range << " " << a << " " << b << endl; int r = 0; bool leftOk = 0; bool rightOk = 0; while (a / 2 != b / 2) { debug cout << "ge1 " << range << " " << a << " " << b << " r " << r << endl; if (a % 2 == 0) leftOk = 1; if (b % 2 == 1) rightOk = 1; if (a + 1 != b) { if (a % 2 == 0) improve(r, val(a + 1)); if (b % 2 == 1) improve(r, val(b - 1)); } if (leftOk) improve(r, added(a / 2)); if (rightOk) improve(r, added(b / 2)); a /= 2; b /= 2; } while (a / 2) { debug cout << "ge2 " << range << " " << a << " " << b << " r " << r << endl; improve(r, added(a / 2)); a /= 2; } debug cout << "ge3 " << range << " " << a << " " << b << " r " << r << endl; return r; } int getAny() { return val(1); } }; const int Tree::s = 1048576; Tree tree; void consume(int i, int j) { minE(rects[i].y1, rects[j].y1); maxE(rects[i].y2, rects[j].y2); maxE(rects[i].x2, rects[j].x2); minE(rects[i].x1, rects[j].x1); } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; REP (i, n) { Rect r; cin >> r.x1 >> r.x2 >> r.y1 >> r.y2; rects.pb(r); } sort(ALL(rects), cmpX1); rects.insert(rects.begin(), defaultRect()); vector<vector<int> > result; REP (i, SIZE(rects)) if (i) { while (true) { int ri = tree.get(rects[i]); Rect& me = rects[i]; Rect& r = rects[ri]; if (r.x2 > me.x1) { debug cout << me << " consumes " << r << endl; consume(i, ri); tree.remove(ri); continue; } break; } tree.put(i); } while (true) { int top = tree.getAny(); if (!top) break; tree.remove(top); Rect& r = rects[top]; vector<int> four; four.pb(r.x1); four.pb(r.x2); four.pb(r.y1); four.pb(r.y2); result.pb(four); } sort(ALL(result)); cout << SIZE(result) << endl; FOREACH (i, result) { FOREACH (j, *i) cout << *j << " "; cout << endl; } return 0; } |