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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int n;
vector<vector<int> > P;

// false - poczatek, true - koniec
struct ev_cmp{
    bool operator()(pair<int,bool> ev1, pair<int,bool> ev2){
        int y1 = P[ev1.first][2+ev1.second];
        int y2 = P[ev2.first][2+ev2.second];

        if (y1!=y2) return y1<y2;
        if (ev1.second!=ev2.second) return ev1.second>ev2.second;
        return ev1<ev2;
    }
};


bool collapsing(int &id, int &id2){
    set<pair<int,bool>, ev_cmp> EventsSet;
    set<pair<int,int> > sweep;

    for(int i=0; i<P.size(); ++i){
        EventsSet.insert(make_pair(i, false));
        EventsSet.insert(make_pair(i, true));
    }

    // Zamiatanie
    for(set<pair<int,bool>, ev_cmp>::iterator it = EventsSet.begin(); it!=EventsSet.end(); ++it){

        // Wyciagnij zdarzenie
        id = it->first;
        bool ending = it->second;
        int X1 = P[id][0], X2 = P[id][1];

        // Koniec prostokata
        if (ending) sweep.erase(make_pair(X1, id));

        // Poczatek prostokata
        else {
            set<pair<int,int> >::iterator it = sweep.lower_bound(make_pair(X1, -1));

            // Sprawdzanie znalezionego
            if (it != sweep.end()){
                id2 = it->second;
                int x = P[id2][0];
                if (x<X2) return true;
            }

            // Sprawdzanie poprzednika
            if (it != sweep.begin()){
                --it; id2 = it->second;
                int x = P[id2][1];
                if (x>X1) return true;
            }

            // Dodawanie przedzialu
            sweep.insert(make_pair(X1, id));
        }
    }
    return false;
}

int main(){

    // Wczytywanie danych
    scanf("%d", &n);
    P.resize(n, vector<int>(4));
    for(int i=0; i<n; ++i) scanf("%d %d %d %d", &P[i][0], &P[i][1], &P[i][2], &P[i][3]);

    // Algorytm
    while(true){
        int P1, P2;
        vector<int> newP(4);
        if(collapsing(P1, P2)){
            if (P1>P2) swap(P1, P2);
            newP[0] = min(P[P1][0], P[P2][0]);
            newP[1] = max(P[P1][1], P[P2][1]);
            newP[2] = min(P[P1][2], P[P2][2]);
            newP[3] = max(P[P1][3], P[P2][3]);

            swap(P[P2], P[P.size()-1]); P.pop_back();
            swap(P[P1], P[P.size()-1]); P.pop_back();
            P.push_back(newP);
        } else break;
    }

    // Wypisywanie wyniku
    printf("%d\n", P.size());
    sort(P.begin(), P.end());
    for(int i=0; i<P.size(); ++i) printf("%d %d %d %d\n", P[i][0], P[i][1], P[i][2], P[i][3]);

}