#include #include #include #include #include using namespace std; struct interval { bool bottom; int y; int x1, x2; }; bool operator< (const interval &a, const interval &b) { if (a.y != b.y) return a.y < b.y; if (a.bottom != b.bottom) return !a.bottom; if (a.x1 != b.x1) return a.x1 < b.x1; if (a.x2 != b.x2) return a.x2 < b.x2; return false; } struct inter { int left, right, height; inter() {} inter(int left, int right, int height) : left(left), right(right), height(height) {} }; int n, w, h, wantw, wanth; int miny, minx; bool won; bool check_finished(const vector &v, int cury) { for (vector::const_iterator it = v.begin(); it != v.end(); ++it) { if (cury - it->height >= wanth && it->right - it->left >= wantw) { if (!won) { won = true; miny = it->height; minx = it->left; } else if (miny > it->height || (miny == it->height && minx > it->left)) { miny = it->height; minx = it->left; } } } return won; } vector update(const vector &v, const interval &i, int cury) { vector res; for (vector::const_iterator it = v.begin(); it != v.end(); ++it) { if (max(it->left, i.x1) > min(it->right, i.x2)) { res.push_back(*it); continue; } if (i.bottom) { inter tmp; tmp.height = it->height; tmp.left = it->left; tmp.right = i.x1; if (tmp.right - tmp.left > 0) res.push_back(tmp); tmp.left = i.x2; tmp.right = it->right; if (tmp.right - tmp.left > 0) res.push_back(tmp); } else { res.push_back(*it); res.push_back(inter(min(it->left, i.x1), max(it->right, i.x2), cury)); } } if (!i.bottom) res.push_back(inter(i.x1, i.x2, i.y)); return res; } void dump_inter(const vector &vec) { cout << "current free intervals" << endl; for (vector::const_iterator it = vec.begin(); it != vec.end(); ++it) cout << it->left << " " << it->right << " " << it->height << endl; cout << endl; } vector simplify(vector v) { bool done = false; vector res; while (!done) { done = true; res.clear(); for (int i = 0; i < v.size(); i++) for (int j = i+1; j < v.size(); j++) if (max(v[i].left, v[j].left) <= min(v[i].right, v[j].right)) { if (v[i].left >= v[j].left && v[i].right <= v[j].right && v[i].height >= v[j].height) { // cout << "case 1: " << i << " " << j << endl; for (int k = 0; k < v.size(); k++) if (k != i) res.push_back(v[k]); done = false; goto next; } else if (v[j].left >= v[i].left && v[j].right <= v[i].right && v[j].height >= v[i].height) { // cout << "case 1': " << i << " " << j << endl; for (int k = 0; k < v.size(); k++) if (k != j) res.push_back(v[k]); done = false; goto next; } else if (v[i].left >= v[j].left && v[i].right <= v[j].right) continue; else if (v[j].left >= v[i].left && v[j].right <= v[i].right) continue; else { // cout << "case 2: " << i << " " << j << endl; inter next(min(v[i].left, v[j].left), max(v[i].right, v[j].right), max(v[i].height, v[j].height)); res.push_back(next); for (int k = 0; k < v.size(); k++) if ((k != i && k != j) || (k == i && v[i].height < next.height) || (k == j && v[j].height < next.height)) res.push_back(v[k]); done = false; goto next; } } continue; next: v = res; // dump_inter(res); } return v; } int main() { ifstream in("decorate.in"); int kases; for (in >> kases; kases; kases--) { vector vec; in >> n >> w >> h; for (int i = 0; i < n; i++) { interval i1, i2; int x1, x2, y1, y2; in >> x1 >> y1 >> x2 >> y2; i1.x1 = i2.x1 = x1; i1.x2 = i2.x2 = x2; i1.y = y1; i2.y = y2; i1.bottom = true; i2.bottom = false; vec.push_back(i1); vec.push_back(i2); } interval tmp_int; tmp_int.y = h; tmp_int.x1 = tmp_int.x2 = 0; tmp_int.bottom = true; vec.push_back(tmp_int); in >> wantw >> wanth; sort(vec.begin(), vec.end()); int acth = 0; won = false; vector current; current.push_back(inter(0, w, 0)); for (vector::iterator inter_it = vec.begin(); inter_it != vec.end(); ) { acth = inter_it->y; // cout << "check... " << acth << endl; if (check_finished(current, acth)) break; // dump_inter(current); while (inter_it->y == acth) { current = update(current, *inter_it, acth); // cout << "insert " << inter_it->x1 << " " << inter_it->x2 << " " << inter_it->y << " " << inter_it->bottom << endl; // dump_inter(current); inter_it++; } // cout << "simplify..." << endl; current = simplify(current); // dump_inter(current); } if (won) cout << minx << " " << miny << endl; else cout << "Fail!" << endl; } return 0; }