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
#include <bits/stdc++.h>

using namespace std;

const int N = 500005, BASE = (1 << 20);

int n, X1, Y1, x2, y2, X, Y;
pair<int, int> tree[6 * N];
int dod[6 * N];
int cnt[2 * N];
vector<pair<int, int> > xs, ys;

pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) {
        return {a.first, a.second + b.second};
    }
    return max(a, b);
}

void insert(int posa, int posb, int w) {
//     cerr << "insert " << posa << " " << posb << " " << w << endl;
    if (posa > posb) return;
    posa += BASE;
    posb += BASE;
    tree[posa].first += w;
    dod[posa] += w;
    if (posa != posb) {
        tree[posb].first += w;
        dod[posb] += w;
    }
    
    while (posa >= 1) {
        if (posa / 2 != posb / 2) {
            if (posa % 2 == 0) {
                tree[posa + 1].first += w;
                dod[posa + 1] += w;
            }
            if (posb % 2 == 1) {
                tree[posb - 1].first += w;
                dod[posb - 1] += w;
            }
        }
        
        posa /= 2;
        posb /= 2;
        tree[posa] = merge(tree[2 * posa], tree[2 * posa + 1]);
        tree[posa].first += dod[posa];
        tree[posb] = merge(tree[2 * posb], tree[2 * posb + 1]);
        tree[posb].first += dod[posb];
    }
}

int solve(vector<pair<int, int> > intervals, int m) {
    vector<pair<int, pair<int, int> > > points;
    for (int i = 0; i < intervals.size(); i++) {
        points.push_back({intervals[i].first, {i, 0}});
        points.push_back({intervals[i].second, {i, 1}});
    }
    sort(points.begin(), points.end());
    int id = 1;
    int last = 0;
    for (int i = 0; i < points.size(); i++) {
        if (points[i].first != last) {
            cnt[id] = points[i].first - last;
            id++;
        }
        if (points[i].second.second == 0) {
            intervals[points[i].second.first].first = id;
        } else {
            intervals[points[i].second.first].second = id - 1;
        }
        last = points[i].first;
    }
//     if (last < m) {
        cnt[id] = m - last;
//     }
//         id--;
//     }

//     for (int i = 1; i <= id; i++) {
//         cerr << cnt[i] << " ";
//     }
//     cerr << endl;
//     for (int i = 0; i < intervals.size(); i++) {
//         cerr << intervals[i].first << " " << intervals[i].second << endl;
//     }
//     BASE = 1;
//     while (BASE <= id) {
//         BASE *= 2;
//     }
    for (int i = 1; i < 2 * BASE; i++) {
        tree[i] = {0, 0};
        dod[i] = 0;
    }
    for (int i = 1; i <= id; i++) {
        tree[i + BASE] = {0, cnt[i]};
    }
    for (int i = BASE - 1; i >= 1; i--) {
        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    
    vector<pair<int, pair<int, int> > > events; 
    for (int i = 0; i < intervals.size(); i++) {
        events.push_back({intervals[i].first, {0, i}});
        events.push_back({intervals[i].second, {1, i}});
    }
    sort(events.begin(), events.end());
    
    for (auto p : intervals) {
        int from = p.first;
        int to = p.second;
        insert(1, from - 1, 1);
        insert(to + 1, id, 1);
    }
    
    int ans = tree[1].first == n ? tree[1].second : 0;
    for (int i = 0; i < events.size(); i++) {
        int w = events[i].second.second;
        int type = events[i].second.first;
        if (type == 0) {
            insert(1, intervals[w].first - 1, -1);
            insert(intervals[w].second + 1, id, -1);
            insert(intervals[w].first, intervals[w].second, 1);
        } else {
            insert(1, intervals[w].first - 1, 1);
            insert(intervals[w].second + 1, id, 1);
            insert(intervals[w].first, intervals[w].second, -1);
        }
//         cerr << "max " << tree[1].first << " " << tree[1].second << endl;
        ans = max(ans, tree[1].first == n ? tree[1].second : 0);
    }
//     cerr << "ans = " << ans << endl;
    return ans;
}

int main() {
    
    scanf("%d %d %d", &n, &X, &Y);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &X1, &Y1, &x2, &y2);
        if (X1 > x2) {
            swap(X1, x2);
        }
        if (Y1 > y2) {
            swap(Y1, y2);
        }
        xs.push_back({X1, x2});
        ys.push_back({Y1, y2});
    }
    
    int yLen = solve(ys, Y);
    int xLen = solve(xs, X);
    
    printf("%lld\n", (long long)xLen * yLen);
    
    return 0;
}