Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <unordered_set>
- using namespace std;
- #define st first
- #define nd second
- #define pb push_back
- #define mp make_pair
- #define klar(v) memset(v, 0, sizeof(v))
- #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define gcd(a, b) __gcd(a, b);
- #define debug(x) cout << #x << " " << x << endl;
- #define endl "\n"
- typedef vector<int> vi;
- typedef vector<pair<int, int> > vpii;
- typedef vector<long long> vll;
- typedef pair<int, int> pii;
- typedef pair<long long, long long> pll;
- typedef long long ll;
- const int maxn = 5e5+100;
- bool testCase();
- struct rect{
- pii l, r;
- };
- int X, Y, n;
- ll ans = 0;
- vector <rect> vec;
- vi mem;
- vll answers;
- int bplane[1234][1234];
- vector <rect> trans_rec(rect x, int mode){
- vector <rect> ret;
- switch(mode){
- case 0:
- ret.pb(x);
- break;
- case 1:
- ret.pb({
- { x.l.st, 1 },
- { x.r.st, x.l.nd-1 }
- });
- ret.pb({
- { x.l.st, x.r.nd+1 },
- { x.r.st, Y }
- });
- break;
- case 2:
- ret.pb({
- { 1, x.l.nd },
- { x.l.st - 1, x.r.nd }
- });
- ret.pb({
- { x.r.st + 1, x.l.nd },
- { X, x.r.nd }
- });
- break;
- case 3:
- ret.pb({
- { 1, 1 },
- { x.l.st - 1, x.l.nd - 1 }
- });
- ret.pb({
- { 1, x.r.nd + 1 },
- { x.l.st - 1, Y }
- });
- ret.pb({
- { x.r.st + 1, x.r.nd + 1},
- { X, Y }
- });
- ret.pb({
- { x.r.st + 1, 1 },
- { X, x.l.nd - 1 }
- });
- break;
- }
- return ret;
- }
- ll ssingle(rect x){
- return 1LL * (x.r.st - x.l.st + 1) * ( x.r.nd - x.l.nd + 1);
- }
- ll size(rect x, int mode){
- ll ret = 0;
- vector <rect> plane;
- plane = trans_rec(x, mode);
- for(auto i: plane){
- ret += ssingle(i);
- }
- return ret;
- }
- ll plane_ans(vector <rect> plane){
- klar(bplane);
- ll ans = 0;
- for(int i = 0; i < plane.size(); i++){
- rect a = plane[i];
- bplane[a.l.nd][a.l.st] += 1;
- bplane[a.l.nd][a.r.st+1] -= 1;
- bplane[a.r.nd+1][a.l.st] -= 1;
- bplane[a.r.nd+1][a.r.st+1] += 1;
- }
- for(int i = 1; i <= Y; i++){
- for(int j = 1; j <= X; j++){
- if(i - 1 >= 0)
- bplane[i][j] += bplane[i-1][j];
- if(j - 1 >= 0)
- bplane[i][j] += bplane[i][j-1];
- if(i - 1 >= 0 && j - 1 >= 0)
- bplane[i][j] -= bplane[i-1][j-1];
- if(bplane[i][j] == n)
- ans++;
- }
- }
- /* for(int i = 1; i <= Y; i++){ */
- /* for(int j = 1; j <= X; j++){ */
- /* cout << bplane[i][j] << " "; */
- /* } */
- /* cout << endl; */
- /* } */
- /* cout << ans << endl; */
- return ans;
- }
- void back(int depth, vector<int> modes){
- if(depth == n){
- vector <rect> tempr, plane;
- for(int i = 0; i < n; i++){
- tempr = trans_rec(vec[i], modes[i]);
- for(auto j: tempr)
- plane.pb(j);
- }
- ll gans = plane_ans(plane);
- ans = max(ans, gans);
- return;
- }
- for(int i = 0; i < 4; i++){
- modes.pb(i);
- back(depth+1, modes);
- modes.pop_back();
- }
- }
- int main(){
- cin >> n >> X >> Y;
- for(int i = 0; i < n; i++){
- int a, b, c, d;
- cin >> a >> b >> c >> d;
- if(a > c) swap(a, c);
- if(b > d) swap(b, d);
- vec.pb({
- { a + 1, b + 1 },
- { c, d }
- });
- }
- vector <int> modes;
- back(0, modes);
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement