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

using ll = long long;

ll solve_1dim(int n, int x_max, vector<pair<int,int>> &seg) {
    vector<pair<int,int>> points; // (x, +/-id)
    vector<int> where_beg(n + 1); // x

    for (int i = 0; i < n; i++) {
        points.emplace_back(seg[i].first, (i + 1));
        points.emplace_back(seg[i].second, -(i + 1));
        where_beg[i + 1] = seg[i].first;
    }

    sort(points.begin(), points.end());
    points.emplace_back(x_max, 0);
    
    vector<int> vis(n + 1);
    stack<int> active_beg; // id
    stack<pair<int,int>> active_seg; // (id, len)

    int res = 0;
    int x = 0;

    active_beg.emplace(0);

    for (auto p : points) {
        if (p.first > x) { // new segment
            while (vis[active_beg.top()]) {
                active_beg.pop();
            }

            if (!active_seg.empty() && active_seg.top().first == active_beg.top()) {
                active_seg.top().second += p.first - x;
            }
            else {
                active_seg.emplace(active_beg.top(), p.first - x);
            }

            x = p.first;
        }

        if (p.second > 0) { // begin
            active_beg.push(p.second);
        }
        else { // end
            int i = (-1) * p.second;

            while (!active_seg.empty() && where_beg[active_seg.top().first] >= where_beg[i]) {
                res = max(res, active_seg.top().second);
                active_seg.pop();
            }

            vis[i] = true;
        }
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false);

    int n, x, y;
    cin >> n >> x >> y;

    vector<pair<int,int>> x_seg(n), y_seg(n);
    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);
        }

        x_seg[i] = make_pair(x1, x2);
        y_seg[i] = make_pair(y1, y2);
    }

    cout << solve_1dim(n, x, x_seg) * solve_1dim(n, y, y_seg) << "\n";
}