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
#include <iostream>
#include <deque>
#include <array>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <cassert>
#include <random>
using namespace std;

int W, H;

template<typename A, typename B>
ostream& operator<<(ostream& o, const pair<A,B>& d){
    o << "(" << d.first << ", " << d.second << ")";
    return o;
}

template<typename T>
ostream& operator<<(ostream& o, const vector<T>& d){
    o << "[";
    for (const T&i:d) o << i << ", ";
    o  <<"]";
    return o;
}

struct Rect {
    int x1,y1;
    int x2,y2;

    bool empty() { return !(x1 < x2 && y1 < y2); }
    long long area() { return ((long long)(x2-x1))*(y2-y1); }

    friend ostream& operator<<(ostream& o, Rect r) {
        o <<"["<<r.x1 << "," <<r.y1 << "," << r.x2 << ","<<r.y2<<"]";
        return o;
    }

};

vector<uint32_t> random_nums;

void init_rand() {
    std::mt19937_64 gen;
    std::uniform_int_distribution<uint32_t> dis;

    for (int i=0; i < 510000 * 4; i ++) {
        random_nums.push_back(dis(gen));
    }
}

struct Hstring {
    static constexpr int VALS = 4;
    array<uint32_t, VALS> state;

    Hstring() {

    }

    bool operator==(const Hstring& o) const {
        return state == o.state;
    }

    bool operator<(const Hstring& o) const {
        return state < o.state;
    }

    void push_back(char c) {
        assert(c == '0');
    }

    void set_at(int i, char c) {
        assert(c == '0' || c == '1');
        int sign = c == '1' ? +1 : -1;

        for (int z=0; z < VALS; z++) {
            state[z] += random_nums[VALS * i + z] * sign;
        }
    }
};

struct Hstring_hash {
    size_t operator() (const Hstring& h) const {
        return h.state[0];
    }
};
//using Hstring = string;

long long solve(vector<pair<int, int> > s, int S) {
    vector<pair<int, pair<bool, int> > > events;
    Hstring state;
    for (int i=0; i < (int)s.size(); i++) {
        state.push_back('0');
        events.emplace_back(0, make_pair(false, i));
        events.emplace_back(s[i].first, make_pair(true, i));
        events.emplace_back(s[i].second, make_pair(false, i));
        events.emplace_back(S, make_pair(true, i));
    }

    sort(events.begin(), events.end());

    int last = 0;
    unordered_map<Hstring, long long, Hstring_hash> result;

    //cerr << "xxx" <<endl;
    for (auto& ev : events) {
        int pos = ev.first;
        if (pos != last)
            result[state] += pos - last;
        //cerr <<"state " << state <<  " " << result[state] << endl;
        last = pos;

        bool target_state = ev.second.first;
        int target_item = ev.second.second;
        state.set_at(target_item, target_state ? '1' : '0');
    }

    long long r = 0;
    for (auto&v: result)r=max(r, v.second);
    return r;
}

int main() {
    ios_base::sync_with_stdio(0);
    init_rand();
    int n;
    cin >> n >> W >> H;

    vector<pair<int, int>> events_x;
    vector<pair<int, int>> events_y;

    vector<pair<int, int>> rx;
    vector<pair<int, int>> ry;

    for (int i=0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >>x1>>y1>>x2>>y2;
        if (x1 > x2)swap(x1,x2);
        if (y1 > y2)swap(y1,y2);
        rx.emplace_back(x1,x2);
        ry.emplace_back(y1,y2);
    }

    long long sx = solve(rx, W);
    long long sy = solve(ry, H);
    cout << sx * sy << endl;
    return 0;
}