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
/*#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif//*/
#include <cstdio>
#include <algorithm>
using namespace std;

const int MaxTerritories = 100000;

struct Territory {
  int x1, x2;
  int y1, y2;
  bool valid;

  friend bool operator<(const Territory& lhs, const Territory& rhs) {
    if(lhs.x1 == rhs.x1)
      return lhs.y1 < rhs.y1;
    return lhs.x1 < rhs.x1;
  }

  friend bool Connect(Territory& lhs, Territory& rhs) {
    if(lhs.y1 >= rhs.y2 || lhs.y2 <= rhs.y1)
      return false;             // no common field
    if(lhs.x2 < rhs.x2)
      lhs.x2 = rhs.x2;
    if(lhs.y1 > rhs.y1)
      lhs.y1 = rhs.y1;
    if(lhs.y2 < rhs.y2)
      lhs.y2 = rhs.y2;
    rhs.valid = false;          // connected to another
    return true;
  }
};

bool lexicographically(const Territory& lhs, const Territory& rhs) {
  if(!lhs.valid)
    return false;
  if(!rhs.valid)
    return true;
  if(lhs.x1 < rhs.x1)
    return true;
  if(lhs.x1 > rhs.x1)
    return false;
  if(lhs.x2 < rhs.x2)
    return true;
  if(lhs.x2 > rhs.x2)
    return true;
  if(lhs.y1 < rhs.y1)
    return true;
  if(lhs.y1 > rhs.y1)
    return false;
  if(lhs.y2 < rhs.y2)
    return true;
  if(lhs.y2 > rhs.y2)
    return true;
  return true;    // two identical?
  }

Territory territories[MaxTerritories];

int main() {
  int n;
  scanf("%d", &n);
  int result = n;
  for(int i = 0; i < n; ++i) {
    scanf("%d%d%d%d", &territories[i].x1, &territories[i].x2, &territories[i].y1, &territories[i].y2);
    territories[i].valid = true;
  }
  sort(territories, territories + n);

  for(bool cont = true; cont; ) {
    cont = false;
    for(int i = 0; i < n; ++i) {
      if(!territories[i].valid)
        continue;
      int x2 = territories[i].x2;
      for(int j = i + 1; j < n && x2 > territories[j].x1; ++j)
        if(territories[j].valid && Connect(territories[i], territories[j])) {
          cont = true;
          --result;
        }
    }
  }

  printf("%d\n", result);
  sort(territories, territories + n, lexicographically);
  for(int i = 0; i < result; ++i)
    if(territories[i].valid)
      printf("%d %d %d %d\n", territories[i].x1, territories[i].x2, territories[i].y1, territories[i].y2);
  return 0;
}