Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3. using namespace std;
  4.  
  5. #define st first
  6. #define nd second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define klar(v) memset(v, 0, sizeof(v))
  10. #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  11. #define gcd(a, b) __gcd(a, b);
  12. #define debug(x) cout << #x << " " << x << endl;
  13. #define endl "\n"
  14.  
  15. typedef vector<int> vi;
  16. typedef vector<pair<int, int> > vpii;
  17. typedef vector<long long> vll;
  18. typedef pair<int, int> pii;
  19. typedef pair<long long, long long> pll;
  20. typedef long long ll;
  21. const int maxn = 5e5+100;
  22.  
  23. bool testCase();
  24.  
  25. struct rect{
  26.     pii l, r;
  27. };
  28.  
  29. int X, Y, n;
  30. ll ans = 0;
  31.  
  32. vector <rect> vec;
  33. vi mem;
  34. vll answers;
  35. int bplane[1234][1234];
  36.  
  37. vector <rect> trans_rec(rect x, int mode){
  38.     vector <rect> ret;
  39.     switch(mode){
  40.         case 0:
  41.             ret.pb(x);
  42.             break;
  43.         case 1:
  44.             ret.pb({
  45.                 { x.l.st, 1 },
  46.                 { x.r.st, x.l.nd-1 }
  47.             });
  48.             ret.pb({
  49.                 { x.l.st, x.r.nd+1 },
  50.                 { x.r.st, Y }
  51.             });
  52.             break;
  53.         case 2:
  54.             ret.pb({
  55.                 { 1, x.l.nd },
  56.                 { x.l.st - 1, x.r.nd }
  57.             });
  58.             ret.pb({
  59.                 { x.r.st + 1, x.l.nd },
  60.                 { X, x.r.nd }
  61.             });
  62.             break;
  63.         case 3:
  64.             ret.pb({
  65.                 { 1, 1 },
  66.                 { x.l.st - 1, x.l.nd - 1 }
  67.             });
  68.             ret.pb({
  69.                 { 1, x.r.nd + 1 },
  70.                 { x.l.st - 1, Y }
  71.             });
  72.             ret.pb({
  73.                 { x.r.st + 1, x.r.nd + 1},
  74.                 { X, Y }
  75.             });
  76.             ret.pb({
  77.                 { x.r.st + 1, 1 },
  78.                 { X, x.l.nd - 1 }
  79.             });
  80.             break;
  81.     }
  82.     return ret;
  83. }
  84.  
  85. ll ssingle(rect x){
  86.     return 1LL * (x.r.st - x.l.st + 1) * ( x.r.nd - x.l.nd + 1);
  87. }
  88.  
  89. ll size(rect x, int mode){
  90.     ll ret = 0;
  91.     vector <rect> plane;
  92.     plane = trans_rec(x, mode);
  93.     for(auto i: plane){
  94.         ret += ssingle(i);
  95.     }
  96.     return ret;
  97. }
  98.  
  99. ll plane_ans(vector <rect> plane){
  100.     klar(bplane);
  101.     ll ans = 0;
  102.     for(int i = 0; i < plane.size(); i++){
  103.         rect a = plane[i];
  104.         bplane[a.l.nd][a.l.st] += 1;
  105.         bplane[a.l.nd][a.r.st+1] -= 1;
  106.         bplane[a.r.nd+1][a.l.st] -= 1;
  107.         bplane[a.r.nd+1][a.r.st+1] += 1;
  108.     }
  109.     for(int i = 1; i <= Y; i++){
  110.         for(int j = 1; j <= X; j++){
  111.             if(i - 1 >= 0)
  112.                 bplane[i][j] += bplane[i-1][j];
  113.             if(j - 1 >= 0)
  114.                 bplane[i][j] += bplane[i][j-1];
  115.             if(i - 1 >= 0 && j - 1 >= 0)
  116.                 bplane[i][j] -= bplane[i-1][j-1];
  117.             if(bplane[i][j] == n)
  118.                 ans++;
  119.         }
  120.     }
  121.     /* for(int i = 1; i <= Y; i++){ */
  122.     /*     for(int j = 1; j <= X; j++){ */
  123.     /*         cout << bplane[i][j] << " "; */
  124.     /*     } */
  125.     /*     cout << endl; */
  126.     /* } */
  127.     /* cout << ans << endl; */
  128.     return ans;
  129. }
  130.  
  131. void back(int depth, vector<int> modes){
  132.     if(depth == n){
  133.         vector <rect> tempr, plane;
  134.         for(int i = 0; i < n; i++){
  135.             tempr = trans_rec(vec[i], modes[i]);
  136.             for(auto j: tempr)
  137.                 plane.pb(j);
  138.         }
  139.         ll gans = plane_ans(plane);
  140.         ans = max(ans, gans);
  141.         return;
  142.     }
  143.     for(int i = 0; i < 4; i++){
  144.         modes.pb(i);
  145.         back(depth+1, modes);
  146.         modes.pop_back();
  147.     }
  148. }
  149.  
  150.  
  151. int main(){
  152.     cin >> n >> X >> Y;
  153.     for(int i = 0; i < n; i++){
  154.         int a, b, c, d;
  155.         cin >> a >> b >> c >> d;
  156.         if(a > c) swap(a, c);
  157.         if(b > d) swap(b, d);
  158.         vec.pb({
  159.             { a + 1, b + 1 },
  160.             { c, d }
  161.         });
  162.     }
  163.     vector <int> modes;
  164.     back(0, modes);
  165.     cout << ans << endl;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement