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
#include <algorithm>
#include <list>
#include <vector>
#include <cassert>
#include <iostream>
#include <sstream>
using namespace std;

struct Rectangle
{
    Rectangle() { }
    Rectangle(int x1, int y1, int x2, int y2)
        : x1_(x1), y1_(y1), x2_(x2), y2_(y2)
    {
    }

    bool operator & (const Rectangle & r) const
    {
        return max(x1_, r.x1_) < min(x2_, r.x2_) and max(y1_, r.y1_) < min(y2_, r.y2_);
    }
    
    bool contains(const Rectangle & r) const
    {
        return x1_ <= r.x1_ and x2_ >= r.x2_ and y1_ <= r.y1_ and y2_ >= r.y2_;
    }
    Rectangle & operator &= (const Rectangle & r)
    {
        x1_ = min(x1_, r.x1_);
        y1_ = min(y1_, r.y1_);
        x2_ = max(x2_, r.x2_);
        y2_ = max(y2_, r.y2_);
        return *this;
    }
    bool operator < (const Rectangle r) const
    {
        if (x1_ != r.x1_)
            return x1_ < r.x1_;
        if (x2_ != r.x2_)
            return x2_ < r.x2_;
        if (y1_ != r.y1_)
            return y1_ < r.y1_;
        return y2_ < r.y2_;
    }
    friend ostream & operator << (ostream & os, const Rectangle &r)
    {
        os << r.x1_ << ' ' << r.x2_ << ' ' << r.y1_ << ' ' << r.y2_;
        return os;
    }
    friend istream & operator >> (istream & is, Rectangle & r)
    {
        is >> r.x1_ >> r.x2_ >> r.y1_ >> r.y2_;
        return is;
    }
private:
    int x1_, y1_, x2_, y2_;
};

int main()
{
    int n;
    cin >> n;
    list<Rectangle> rectangles;
    typedef list<Rectangle>::iterator RecIter;
    vector<Rectangle> rectangles2;
    rectangles2.reserve(n);
    for (int i = 0 ; i < n ; i++)
    {
        Rectangle current;
        cin >> current;
        rectangles2.push_back(current); 
    } 
    random_shuffle(rectangles2.begin(), rectangles2.end()); 
    for (int i = 0 ; i < n ; i++)
    {
        Rectangle current = rectangles2[i];
        
        bool cont = true;
        bool eaten = false;
        while(cont)
        {
            cont = false;
            for (RecIter it = rectangles.begin(); it != rectangles.end();)
            {
                if (current.contains(*it))
                {
                    it = rectangles.erase(it);
                }
                else if(it->contains(current))
                {
                    assert(cont == false);
                    eaten = true;
                    break;
                }
                else if (*it & current)
                {
                    cont = true;
                    current &= *it;
                    it = rectangles.erase(it);
                }
                else
                    ++it;
            }
        }
        if (!eaten)
            rectangles.push_back(current);
    }
    
    rectangles.sort();
    cout << rectangles.size() << '\n';
    for (RecIter it = rectangles.begin(); it != rectangles.end(); ++it)
        std::cout << *it << '\n';
}