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
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pii;

const ull p[] = {
	(ull)1e9 + 7,
	(ull)1e9 + 607,
	(ull)1e9 + 1927
};

struct event { bool start; int x, index; };

bool operator< (const event& a, const event& b) {
	return a.x < b.x;
}

int max_common_len(vector<pii>& spans, int bound) {
	int n = spans.size();
	vector<event> coords(2*n);
	for (int i = 0; i < n; i++) {
		coords[2*i] = { true, spans[i].first, i };
		coords[2*i+1] = { false, spans[i].second, i };
	}

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

	typedef pair<ull, ull> hkey;
	vector<hkey> pp(n);
	pp[0] = { 1, 1 };
	for (int i = 1; i < n; i++) {
		pp[i].first = p[0] * pp[i-1].first;
		pp[i].second = p[1] * pp[i-1].second;
	}

	map<hkey, int> areas;
	hkey h = { 0, 0 };
	int prev_x = 0;

	for (event c : coords) {
		if (c.x != prev_x) {
			if (areas.count(h) == 0) {
				areas[h] = 0;
			}

			areas[h] += c.x - prev_x;
		}

		h.first += (c.start ? 1 : -1) * pp[c.index].first;
		h.second += (c.start ? 1 : -1) * pp[c.index].second;
		prev_x = c.x;
	}

	if (bound != prev_x) {
		if (areas.count(h) == 0) {
			areas[h] = 0;
		}

		areas[h] += bound - prev_x;
	}

	int max_area = 0;
	for (auto a : areas) max_area = max(max_area, a.second);
	return max_area;
}

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

	int n, w, h;
	cin >> n >> w >> h;

	vector<pii> xs(n), ys(n);
	for (int i = 0; i < n; i++) {
		cin >> xs[i].first >> ys[i].first >> xs[i].second >> ys[i].second;
		if (xs[i].first > xs[i].second) swap(xs[i].first, xs[i].second);
		if (ys[i].first > ys[i].second) swap(ys[i].first, ys[i].second);
	}

	ll rx = max_common_len(xs, w);
	ll ry = max_common_len(ys, h);

	cout << rx * ry << endl;

	return 0;
}