fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define __builtin_ctz __builtin_ctzll
  17. #define __builtin_clz __builtin_clzll
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  21. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  22.   while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  23. }
  24. #ifdef LOCAL
  25. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  26. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  27. #else
  28. #define debug(...) (__VA_ARGS__)
  29. #define debugv(x)
  30. #define cerr if(0)cout
  31. #endif
  32. #define next ____next
  33. #define prev ____prev
  34. #define left ____left
  35. #define hash ____hash
  36. typedef long long ll;
  37. typedef long double LD;
  38. typedef pair<int, int> PII;
  39. typedef pair<ll, ll> PLL;
  40. typedef vector<int> VI;
  41. typedef vector<VI> VVI;
  42. typedef vector<ll> VLL;
  43. typedef vector<pair<int, int> > VPII;
  44. typedef vector<pair<ll, ll> > VPLL;
  45.  
  46. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  47. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  48. template<class T1, class T2>
  49. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  50. template<class A, class B, class C> struct Triple { A first; B second; C third;
  51.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  52. template<class T> void ResizeVec(T&, vector<int>) {}
  53. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  54.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  55.   for (T& v : vec) { ResizeVec(v, sz); }
  56. }
  57. typedef Triple<int, int, int> TIII;
  58. template<class A, class B, class C>
  59. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  60. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  61. template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  62. template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  63.  
  64. struct Rec {
  65.   int l, d, r, u;
  66.   friend ostream& operator<<(ostream& out, Rec R) {
  67.     return out<<"("<<R.l<<" - "<<R.r<<") x ("<<R.d<<" - "<<R.u<<")";
  68.   }
  69. };
  70.  
  71. const int N = 1e9 + 5;
  72. int MinU(vector<Rec>& recs) {
  73.   int minu = N;
  74.   for (auto& rec : recs) {
  75.     mini(minu, rec.u);
  76.   }
  77.   return minu;
  78. }
  79. int MinR(vector<Rec>& recs) {
  80.   int minr = N;
  81.   for (auto& rec : recs) {
  82.     mini(minr, rec.r);
  83.   }
  84.   return minr;
  85. }
  86. int MaxL(vector<Rec>& recs) {
  87.   int maxl = 0;
  88.   for (auto& rec : recs) {
  89.     maxi(maxl, rec.l);
  90.   }
  91.   return maxl;
  92. }
  93. int MaxD(vector<Rec>& recs) {
  94.   int maxd = 0;
  95.   for (auto& rec : recs) {
  96.     maxi(maxd, rec.d);
  97.   }
  98.   return maxd;
  99. }
  100. bool Between(int a, int b, int c) {
  101.   return b <= a && a <= c;
  102. }
  103. VPII Go(int k, vector<Rec> recs, VPII sticks) {
  104.   if (recs.empty()) {
  105.     return sticks;
  106.   }
  107.   int minr = MinR(recs);
  108.   int maxl = MaxL(recs);
  109.   int minu = MinU(recs);
  110.   int maxd = MaxD(recs);
  111.   //debug(minr, maxl, minu, maxd);
  112.   if (k == 1) {
  113.     if (maxl > minr || maxd > minu) {
  114.       return {};
  115.     } else {
  116.       sticks.PB({minr, minu});
  117.       return sticks;
  118.     }
  119.   }
  120.   VPII cands{{minr, minu},
  121.              {minr, maxd},
  122.              {maxl, maxd},
  123.              {maxl, minu}};
  124.   for (auto cand : cands) {
  125.     vector<Rec> rems;
  126.     sticks.PB(cand);
  127.     for (auto rec : recs) {
  128.       if (Between(cand.st, rec.l, rec.r) && Between(cand.nd, rec.d, rec.u)) {
  129.       } else {
  130.         rems.PB(rec);
  131.       }
  132.     }
  133.     //debug(cand, rems);
  134.     auto ret = Go(k - 1, rems, sticks);
  135.     if (ret.empty()) {
  136.       sticks.pop_back();
  137.       continue;
  138.     }
  139.     return ret;
  140.   }
  141.   return {};
  142. }
  143. const PII bad{-1, -1};
  144. const int kInf = 1e9;
  145. PII Intersect(PII L, PII R) {
  146.   if (L.nd < R.st || R.nd < L.st) { return bad; }
  147.   return {max(L.st, R.st), min(L.nd, R.nd)};
  148. }
  149. void SelfIntersect(PII& L, PII R) {
  150.   L = Intersect(L, R);
  151. }
  152. bool In(int d, PII p) {
  153.   return Between(d, p.st, p.nd);
  154. }
  155. int32_t main() {
  156.  
  157.   ios_base::sync_with_stdio(0);
  158.   cout << fixed << setprecision(10);
  159.   cerr << fixed << setprecision(10);
  160.   cin.tie(0);
  161.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  162.  
  163.   int n, k;
  164.   cin>>n>>k;
  165.   vector<Rec> recs;
  166.   map<int, int> mapuj;
  167.   RE (i, n) {
  168.     int l, d, r, u;
  169.     cin>>l>>d>>r>>u;
  170.     recs.PB({l, d, r, u});
  171.     mapuj[l];
  172.     mapuj[r];
  173.     mapuj[d];
  174.     mapuj[u];
  175.   }
  176.   int cnt = 0;
  177.   map<int, int> inv;
  178.   for (auto& p : mapuj) {
  179.     cnt++;
  180.     p.nd = cnt;
  181.     inv[cnt] = p.st;
  182.   }
  183.   for (auto& rec : recs) {
  184.     rec.l = mapuj[rec.l];
  185.     rec.r = mapuj[rec.r];
  186.     rec.d = mapuj[rec.d];
  187.     rec.u = mapuj[rec.u];
  188.   }
  189.   auto ret = Go(k, recs, {});
  190.   if (!ret.empty()) {
  191.     while (SZ(ret) < k) {
  192.       ret.PB(ret.back());
  193.     }
  194.     for (auto cand : ret) {
  195.       cout<<inv[cand.st]<<" "<<inv[cand.nd]<<endl;
  196.     }
  197.     return 0;
  198.   }
  199.   debug("hard");
  200.   assert(k == 4);
  201.  
  202.   int minr = MinR(recs);
  203.   int maxl = MaxL(recs);
  204.   int minu = MinU(recs);
  205.   int maxd = MaxD(recs);
  206.   PII intv_l = {minu + 1, maxd - 1};
  207.   PII intv_r = intv_l;
  208.   PII intv_u = {minr + 1, maxl - 1};
  209.   PII intv_d = intv_u;
  210.  
  211.   PII all = {0, kInf};
  212.   VPII up_to_du(cnt + 2, all);
  213.   VPII from_du(cnt + 2, all);
  214.   VPII up_to_lr(cnt + 2, all);
  215.   VPII from_lr(cnt + 2, all);
  216.  
  217.   VI up_to_r(cnt + 2, cnt); // najmniejsze ograniczenie na dolny_x
  218.   VI from_r(cnt + 2, cnt); // najmniejsze ograniczene na gorny_x
  219.   VI from_u(cnt + 2, cnt); // najmniejsze ograniczenie na prawy_y
  220.   VI from_d(cnt + 2, 0); // najwieksze ograniczenie na prawy_y
  221.  
  222.   int minRhor = cnt;
  223.   for (auto rec : recs) {
  224.     int reachR = rec.l <= minr;
  225.     int reachL = rec.r >= maxl;
  226.     int reachU = rec.d <= minu;
  227.     int reachD = rec.u >= maxd;
  228.     int sum = reachR + reachL + reachU + reachD;
  229.     assert(sum);
  230.     if (sum >= 3) { continue; }
  231.     if (sum == 1) {
  232.       if (reachR) {
  233.         SelfIntersect(intv_r, {rec.d, rec.u});
  234.       } else if (reachL) {
  235.         SelfIntersect(intv_l, {rec.d, rec.u});
  236.       } else if (reachD) {
  237.         SelfIntersect(intv_d, {rec.l, rec.r});
  238.       } else {
  239.         SelfIntersect(intv_u, {rec.l, rec.r});
  240.       }
  241.     } else {
  242.       if (reachR && reachL) {
  243.         SelfIntersect(up_to_lr[rec.u], {rec.d, rec.u});
  244.         SelfIntersect(from_lr[rec.d], {rec.d, rec.u});
  245.       } else if (reachU && reachD) {
  246.         SelfIntersect(up_to_du[rec.r], {rec.l, rec.r});
  247.         SelfIntersect(from_du[rec.l], {rec.l, rec.r});
  248.         mini(minRhor, rec.r); 
  249.       } else if (reachR && reachU) {
  250.         mini(up_to_r[rec.u], rec.r);
  251.       } else if (reachU && reachL) {
  252.         mini(from_u[rec.l], rec.u);
  253.       } else if (reachL && reachD) {
  254.         maxi(from_d[rec.l], rec.d);
  255.       } else if (reachD && reachR) {
  256.         mini(from_r[rec.d], rec.r);
  257.       }
  258.     }
  259.   }
  260.   RE (i, cnt) {
  261.     SelfIntersect(up_to_lr[i], up_to_lr[i - 1]);
  262.     SelfIntersect(up_to_du[i], up_to_du[i - 1]);
  263.     mini(up_to_r[i], up_to_r[i - 1]);
  264.   }
  265.   FORD (i, cnt, 1) {
  266.     SelfIntersect(from_lr[i], from_lr[i + 1]);
  267.     SelfIntersect(from_du[i], from_du[i + 1]);
  268.     mini(from_r[i], from_r[i + 1]);
  269.     mini(from_u[i], from_u[i + 1]);
  270.     maxi(from_d[i], from_d[i + 1]);
  271.   }
  272.  
  273.   REP (tr, 2) { // tr == 0 ->  dolny_x < gorny_x
  274.     FOR (lewy_y, intv_r.st, intv_r.nd) {
  275.       int dolny_x, gorny_x;
  276.       if (tr == 0) {
  277.         dolny_x = min({intv_u.nd, minRhor, up_to_r[lewy_y - 1]});
  278.         if (dolny_x == -1) { continue; }
  279.         if (!In(dolny_x, intv_u)) { continue; }
  280.         PII hors = Intersect(intv_d, from_du[dolny_x + 1]);
  281.         gorny_x = min({hors.nd, from_r[lewy_y + 1]});
  282.         if (gorny_x == -1) { continue; }
  283.         if (!In(gorny_x, hors)) { continue; }
  284.       } else {
  285.         gorny_x = min({intv_d.nd, minRhor, from_r[lewy_y + 1]});
  286.         if (gorny_x == -1) { continue; }
  287.         if (!In(gorny_x, intv_d)) { continue; }
  288.         PII hors = Intersect(intv_u, from_du[gorny_x + 1]);
  289.         dolny_x = min(hors.nd, up_to_r[lewy_y - 1]);
  290.         if (dolny_x == -1) { continue; }
  291.         if (!In(dolny_x, hors)) { continue; }
  292.       }
  293.       PII at_prawy = intv_l;
  294.       SelfIntersect(at_prawy, {from_d[gorny_x + 1], cnt});
  295.       SelfIntersect(at_prawy, up_to_lr[lewy_y - 1]);
  296.       SelfIntersect(at_prawy, from_lr[lewy_y + 1]);
  297.       SelfIntersect(at_prawy, {0, from_u[dolny_x + 1]});
  298.       if (at_prawy.nd == -1) { continue; }
  299.       VPII sol{{minr, lewy_y}, {dolny_x, minu}, {gorny_x, maxd}, {maxl, at_prawy.nd}};
  300.       for (auto stick : sol) {
  301.         cout<<inv[stick.st]<<" "<<inv[stick.nd]<<endl;
  302.       }
  303.       for (auto rec : recs) {
  304.         int ok = 0;
  305.         for (auto stick : sol) {
  306.           if (Between(stick.st, rec.l, rec.r) && Between(stick.nd, rec.d, rec.u)) {
  307.             ok = 1;
  308.           }
  309.         }
  310.         assert(ok);
  311.       }
  312.       return 0;
  313.     }
  314.   }
  315.   assert(false);
  316.  
  317.  
  318.   return 0;
  319. }
  320.  
Runtime error #stdin #stdout #stderr 0s 4348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:200: int32_t main(): Assertion `k == 4' failed.
https://ideone.com/RNJXof
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!