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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<string>
#include<set>

typedef unsigned long long ull;

struct Rectangle
{
  ull x1, x2, y1, y2;
  bool operator<(const Rectangle& other) const
  {
    if(x1 != other.x1)
      return x1 < other.x1;
    if(x2 != other.x2)
      return x2 < other.x2;
    if(y1 != other.y1)
      return y1 < other.y1;
    return y2 < other.y2;
  }

  const bool overlaps(const Rectangle& other) const
  {
    return !(x1 >= other.x2 || other.x1 >= x2 || y1 >= other.y2 || other.y1 >= y2);
  }
  
  Rectangle merge(const Rectangle& other) const
  {
    Rectangle result;
    result.x1 = std::min(x1, other.x1);
    result.x2 = std::max(x2, other.x2);
    result.y1 = std::min(y1, other.y1);
    result.y2 = std::max(y2, other.y2);
    return result;
  }
};

typedef std::set<Rectangle> RectanglesSet;

int main(int argc, char** argv)
{
  std::ios_base::sync_with_stdio(false);
  int N;
  std::cin>>N;
  RectanglesSet rectangles;
  for(int i = 0; i < N; ++i)
  {
    Rectangle r;
    std::cin>>r.x1>>r.x2>>r.y1>>r.y2;
    rectangles.insert(r);
  }
  
  RectanglesSet solution;
  RectanglesSet::iterator it;
  bool somethingChanged = true;
  while(somethingChanged)
  {
  it = rectangles.begin();
  somethingChanged = false;
  while(it != rectangles.end())
  {
    bool merged(false);
    RectanglesSet::iterator it2 = it;
    ++it2;
    while(it2 != rectangles.end())
    { 
      if(it->overlaps(*it2))
      {
        merged = true;
        somethingChanged = true;
        Rectangle r = it->merge(*it2);
        rectangles.erase(it);
        rectangles.erase(it2);
        it = rectangles.insert(r).first;
        break;
      } else if(it2->x1 >= it->x2)
      {
        break;
      }
      ++it2;
    }

    if(!merged)
    {
      ++it;
    }
  }
  }
  std::cout<<rectangles.size()<<std::endl;
  for(it = rectangles.begin(); it != rectangles.end(); ++it)
  {
    std::cout<<it->x1<<" "<<it->x2<<" "<<it->y1<<" "<<it->y2<<std::endl; 
  }
  return 0;
}