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 <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <list>

struct Rect
{
    int x1, x2, y1, y2;

    bool operator< (const Rect& rhs)
    {
        if (x1!=rhs.x1) return x1<rhs.x1;
        if (x2!=rhs.x2) return x2<rhs.x2;
        if (y1!=rhs.y1) return y1<rhs.y1;
        return y2<rhs.y2;
    }

    Rect& operator %= (const Rect& other)
    {
        x1 = std::min(x1, other.x1);
        x2 = std::max(x2, other.x2);
        y1 = std::min(y1, other.y1);
        y2 = std::max(y2, other.y2);
        return *this;
    }

    bool contain(const Rect& other)
    {
        return (x1<=other.x1) && (other.x2<x2) && (y1<=other.y1) && (other.y2<=y2);
    }

    bool intersect(const Rect& other)
    {
        return (std::min(x2, other.x2) > std::max(x1, other.x1))
            && (std::min(y2, other.y2) > std::max(y1, other.y1));
    }

    friend std::ostream& operator<< (std::ostream& os, const Rect& rect)
    {
        return os << rect.x1 << ' ' << rect.x2 << ' ' << rect.y1 << ' ' << rect.y2;
    }

    friend std::istream& operator>> (std::istream& is, Rect& rect)
    {
        return is >> rect.x1 >> rect.x2 >> rect.y1 >> rect.y2;
    }
};


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

    int n;
    std::cin >> n;

    std::list<Rect> rects;
    for (int i=0; i<n; ++i)
    {
        Rect current;
        std::cin >> current;

        bool ok = true;
        while (true)
        {
            bool intersect = false;
            for (std::list<Rect>::iterator it=rects.begin(); it!=rects.end();)
            {
                if (it->contain(current)) {
                    ok = false;
                    break;
                } else if (current.contain(*it)) {
                    rects.erase(it++);
                    continue;
                } else if (current.intersect(*it)) {
                    current %= *it;
                    rects.erase(it++);
                    intersect = true;
                    break;
                } else ++it;
            }
            if (!intersect || !ok)
                break;
        }
        if (ok)
            rects.push_back(current);
    }

    rects.sort();
    std::cout << rects.size() << '\n';
    for (std::list<Rect>::iterator it=rects.begin(); it!=rects.end(); ++it)
    {
        std::cout << *it << '\n';
    }

    return 0;
}