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

#define SP set<Point>
#define iter iterator
#define be begin()
#define en end()
#define st first

struct Event{
    int x, y1, y2, j;
    bool f;
    Event() {}
    Event(int a, int b, int c, int d, bool e)
        : x(a), y1(b), y2(c), j(d), f(e) {}
} e[300000];

inline bool operator<(const Event& a, const Event& b){
    return (a.x==b.x?a.f:a.x<b.x);
}

struct Rect{
    int x1, x2, y1, y2, q;
} r[100000];

inline bool operator<(const Rect& a, const Rect& b){
    return (a.x1==b.x1?(a.x2==b.x2?(a.y1==b.y1?(a.y2<b.y2):a.y1<b.y1):a.x2<b.x2):a.x1<b.x1);
}

bool b[100000];

inline void Read(Rect& r){
    scanf("%d%d%d%d", &r.x1, &r.x2, &r.y1, &r.y2);
}

struct Point{
    int y, j;
    bool f;
    Point(int a, int b, bool c)
        : y(a), j(b), f(c) {}
};

inline bool operator==(const Point& a, const Point& b){
    return (a.y==b.y && a.j==b.j && a.f==b.f);
}

inline bool operator<(const Point& a, const Point& b){
    return (a.y==b.y?(a.f==b.f?(a.j<b.j):a.f):a.y<b.y);
}

inline bool Intersect(int a, int b){
    if(a==b) return 0;
    return (r[a].y1<r[b].y2 && r[a].y2>r[b].y1);
}

SP::iter Merge(SP& S, int x, int y){
    SP::iter it;
    b[y]=1;
    S.erase(Point(r[x].y1, x, 0));
    S.erase(Point(r[x].y2, x, 1));
    S.erase(Point(r[y].y1, y, 0));
    S.erase(Point(r[y].y2, y, 1));
    if(r[x].x2<r[y].x2){
        swap(e[r[x].q], e[r[y].q]);
        r[x].q=r[y].q;
    }
    r[x].x1=min(r[x].x1, r[y].x1);
    r[x].x2=max(r[x].x2, r[y].x2);
    r[x].y1=min(r[x].y1, r[y].y1);
    r[x].y2=max(r[x].y2, r[y].y2);
    it=(S.insert(Point(r[x].y1, x, 0))).st;
    S.insert(Point(r[x].y2, x, 1));
    return it;
}

int main()
{
    set<Point> S;
    int n, k=0;
    scanf("%d", &n);
    for(int i=0;i<n;++i){
        Read(r[i]);
        e[k++]=Event(r[i].x1, r[i].y1, r[i].y2, i, 0);
        e[k++]=Event(r[i].x2, r[i].y1, r[i].y2, i, 1);
    }
    sort(e, e+k);
    for(int i=0;i<k;++i)
        if(e[i].f) r[e[i].j].q=i;
    for(int i=0;i<k;++i)
        if(!b[e[i].j]){
            if(e[i].f){
                S.erase(Point(e[i].y1, e[i].j, 0));
                S.erase(Point(e[i].y2, e[i].j, 1));
            }else{
                SP::iter it, it2, it3, it4;
                it3=it2=it=(S.insert(Point(e[i].y1, e[i].j, 0))).st;
                S.insert(Point(e[i].y2, e[i].j, 1));
                while(1){
                    if(Intersect(it->j, it2->j)){
                        it=it2=it3=Merge(S, it->j, it2->j);
                    }else if(it!=S.be && Intersect(it->j, (--it3)->j)){
                        it=it2=it3=Merge(S, it->j, it3->j);
                    }else break;
                }
            }
        }
    int s=0;
    for(int i=0;i<n;++i)
        if(!b[i]) r[s++]=r[i];
    sort(r, r+s);
    printf("%d\n", s);
    for(int i=0;i<s;++i)
        printf("%d %d %d %d\n", r[i].x1, r[i].x2, r[i].y1, r[i].y2);
}