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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <iostream>
#include <map>

using namespace std;

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

    Rect(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
};

bool check(Rect *r1, Rect *r2)
{
    return (
        ((r2->x1 >= r1->x1) && (r2->x1 <= r1->x2) && (r2->y1 >= r1->y1) && (r2->y1 <= r1->y2))
        ||
        ((r2->x2 >= r1->x1) && (r2->x2 <= r1->x2) && (r2->y2 >= r1->y1) && (r2->y2 <= r1->y2))
        ||
        ((r2->x1 >= r1->x1) && (r2->x1 <= r1->x2) && (r2->y2 >= r1->y1) && (r2->y2 <= r1->y2))
        ||
        ((r2->x2 >= r1->x1) && (r2->x2 <= r1->x2) && (r2->y1 >= r1->y1) && (r2->y1 <= r1->y2))
            );
}

multimap<int, Rect*>::iterator find(multimap<int, Rect*>& m, int n, Rect* r)
{
    Rect *f;
    multimap<int, Rect*>::iterator p, k;
    pair<multimap<int, Rect*>::iterator, multimap<int, Rect*>::iterator> range = m.equal_range(n);
    p = range.first;
    k = range.second;
    while (p != k)
    {
        f = p->second;
        if (f == r) return p;
        ++p;
    }
    //cout << "notfound" << endl;
    return m.end();
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

    int n;
    Rect *r;
    multimap<int, Rect*> xs, ys;
    int x1, y1, x2, y2;

    cin >> n;
    while (n--)
    {
        cin >> x1 >> x2 >> y1 >> y2;
        r = new Rect(x1, y1, x2, y2);
        xs.insert(make_pair(x1, r));
        ys.insert(make_pair(y1, r));
    }

    int px, py, kx, ky, changes;
    Rect *r2;
    multimap<int, Rect*>::iterator it, wit, cit, tit;

    //for (it = ys.begin(); it != ys.end(); ++it)
    //{
    //    cout << it->first << ' ' << it->second << endl;
    //}

    do
    {
        changes = 0;
        it = xs.begin();
        while (it != xs.end())
        {
            r = it->second;
            px = r->x1;
            kx = r->x2;

            wit = it;
            ++wit;
            while (wit != xs.end())
            {
                r2 = wit->second;
                cit = wit;
                ++wit;
                if (r2->x1 >= kx) break;
                if (check(r, r2))
                {
                    //cout << r->x1 << ' ' << r->x2 << ' ' << r->y1 << ' ' << r->y2 << ", " << r2->x1 << ' ' << r2->x2 << ' ' << r2->y1 << ' ' << r2->y2 << endl;
                    ++changes;
                    if (r2->y1 < r->y1)
                    {
                        ys.erase(find(ys, r->y1, r));
                        r->y1 = r2->y1;
                        ys.erase(find(ys, r2->y1, r2)); //!
                        ys.insert(make_pair(r->y1, r));
                    }
                    else
                    {
                        tit = find(ys, r2->y1, r2);
                        //cout << "!" << tit->first << ' ' << tit->second << endl;
                        ys.erase(tit);
                        //cout << "!" << tit->first << ' ' << tit->second << endl;
                    }
                    if (r2->y2 > r->y2)
                    {
                        r->y2 = r2->y2;
                    }
                    if (r2->x2 > r->x2)
                    {
                        r->x2 = r2->x2;
                        kx = r2->x2;
                    }
                    xs.erase(cit);
                }

                //for (tit = ys.begin(); tit != ys.end(); ++tit)
                //{
                //    cout << tit->first << ' ' << tit->second << endl;
                //}
            }
            ++it;
        }

        it = ys.begin();
        while (it != ys.end())
        {
            r = it->second;
            py = r->y1;
            ky = r->y2;

            wit = it;
            ++wit;
            while (wit != ys.end())
            {
                r2 = wit->second;
                cit = wit;
                ++wit;
                if (r2->y1 >= ky) break;
                if (check(r, r2))
                {
                    //cout << r->x1 << ' ' << r->x2 << ' ' << r->y1 << ' ' << r->y2 << ", " << r2->x1 << ' ' << r2->x2 << ' ' << r2->y1 << ' ' << r2->y2 << endl;
                    ++changes;
                    if (r2->x1 < r->x1)
                    {
                        xs.erase(find(xs, r->x1, r));
                        r->x1 = r2->x1;
                        xs.erase(find(xs, r2->x1, r2)); //!
                        xs.insert(make_pair(r->x1, r));
                    }
                    else
                    {
                        tit = find(xs, r2->x1, r2);
                        xs.erase(tit);
                    }
                    if (r2->x2 > r->x2)
                    {
                        r->x2 = r2->x2;
                    }
                    if (r2->y2 > r->y2)
                    {
                        r->y2 = r2->y2;
                        ky = r2->y2;
                    }
                    ys.erase(cit);
                }
            }
            ++it;
        }
    } while (changes > 0);

    cout << xs.size() << '\n';
    for (it = xs.begin(); it != xs.end(); ++it)
    {
        r = it->second;
        cout << r->x1 << ' ' << r->x2 << ' ' << r->y1 << ' ' << r->y2 << '\n';
    }
}