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
#include <bits/stdc++.h>
#define N 500007
using namespace std;
int n, xx, yy, x_1, x_2, y_1, y_2;
typedef pair<int, int> range;

bool inside_range(range my_range, int x) {
  return x >= my_range.first && x < my_range.second;
}

vector<range> x_range, y_range;

vector<range> simplify(vector<range> &intervals) {
  //printf("Intervals: ");
  vector<range> result;
  set<range> pool;
  for (int i= 0; i < intervals.size(); i++){
    //printf("%d %d..", intervals[i].first, intervals[i].second);
    pool.insert(intervals[i]);
  }
  //printf("\n");
  set<range> inverted;
  int min_x = 0;
  while(!pool.empty()) {
    //printf("%d\n", pool.size());
    range i = *pool.begin();
    //printf("reading %d %d\n", i.first, i.second);
    pool.erase(pool.begin());
    min_x = max(min_x, i.first);
    if (i.second <= min_x){
      result.push_back(make_pair(i.first, i.second));
      continue;
    }
    if (!inverted.empty()) {
      //printf("Top of the inverted is %d %d\n", inverted.begin()->second, inverted.begin()->first);
    }
    while(!inverted.empty() && inverted.begin()->first <= i.first) {
      //printf("Top of the inverted is %d %d\n", inverted.begin()->second, inverted.begin()->first);
      //printf("And we remove it, as it ends earlier\n");
      result.push_back(make_pair(inverted.begin()->second, inverted.begin()->first));
      inverted.erase(inverted.begin());
    }
    if (!inverted.empty() && inverted.begin()->first <= i.second) {
      //printf("Top of the inverted is %d %d\n", inverted.begin()->second, inverted.begin()->first);
      //printf("And we cut it to %d %d\n", inverted.begin()->second, i.first);
      if (inverted.begin() -> second != i.first) {
        assert (inverted.begin()->second < i.first);
        // is it possible that i.first < inverted.begin()->second
        result.push_back(make_pair(inverted.begin()->second, i.first));
      }
     // printf("Adding to the pool: %d %d + %d %d\n", inverted.begin()->first,
      //    i.second, i.first, inverted.begin()->first);
      if (inverted.begin()->first != i.second) {
        assert (inverted.begin()->first < i.second);
        pool.insert(make_pair(inverted.begin()->first, i.second));
      }
      pool.insert(make_pair(i.first, inverted.begin()->first));
      inverted.erase(inverted.begin());
    } else {
      //printf("We add ourselves to the inverted\n");
      inverted.insert(make_pair(i.second, i.first));
    }
  }
  while(!inverted.empty()){
    result.push_back(make_pair(inverted.begin()->second, inverted.begin()->first));
    inverted.erase(inverted.begin());
  }
  sort(result.begin(), result.end());
  //printf("Final intervals: ");
  for(int i = 0; i < result.size(); i++){
    //printf("%d %d..", result[i].first, result[i].second);
  }
  //printf("\n");
  return result;
}

long long solve(vector<range> &intervals, long long limit){
  long long best = 0ll;
  vector<range> stack;
  vector<long long> lengths;
  long long total = limit;
  for(int i = 0; i < intervals.size(); i++) {
    while (!stack.empty() && !inside_range(stack.back(), intervals[i].first)) {
      //popping
      best = max(best, lengths.back());
      lengths.pop_back();
      stack.pop_back();
    }
    if (!stack.empty()){
      lengths[lengths.size()-1] -= intervals[i].second - intervals[i].first;
    } else {
      total -= intervals[i].second - intervals[i].first;
    }
    stack.push_back(intervals[i]);
    lengths.push_back(intervals[i].second - intervals[i].first);
  }

  while (!stack.empty()) {
    //popping
    best = max(best, lengths.back());
    lengths.pop_back();
    stack.pop_back();
  }
  return max(best, total);
}

int main() {
  scanf("%d%d%d", &n, &xx, &yy);
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d%d", &x_1, &y_1, &x_2, &y_2);
    if (x_1 > x_2) swap(x_1, x_2);
    if (y_1 > y_2) swap(y_1, y_2);
    x_range.push_back(make_pair(x_1, x_2));
    y_range.push_back(make_pair(y_1, y_2));
  }
  //x_range.push_back(make_pair(0, xx));
  //y_range.push_back(make_pair(0, yy));

  x_range = simplify(x_range);
  y_range = simplify(y_range);
  //printf("%d %d\n", x_range.size(), y_range.size());

  long long best_estimate_x = solve(x_range, xx);
  long long best_estimate_y = solve(y_range, yy);
  printf("%lld\n", best_estimate_x * best_estimate_y);
//  printf("%lld %lld\n", best_estimate_x, best_estimate_y);
}