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

struct S{int v1,v2;S(){}S(int v1_,int v2_):v1(v1_),v2(v2_){}};
int haussdorf(int a1,int b1,int a2,int b2){return max(abs(a1-a2),abs(b1-b2));}
struct compS{
    bool operator()(const S &s1,const S &s2)const{
        int h=haussdorf(s1.v1,s1.v2,s2.v1,s2.v2);
        return h==0?false:s1.v1<s2.v1;
    }
};
typedef multimap<S,int,compS> STM;
typedef STM::iterator STMI;
typedef set<int> IS;
typedef IS::iterator ISI;
struct R{int x1,x2,y1,y2;IS l;STMI ref;int u;R(){}R(int x1_,int x2_,int y1_,int y2_):x1(x1_),x2(x2_),y1(y1_),y2(y2_),u(0){}};
struct E{int u,v1,v2,m,i;};
struct BB{
    int x1,x2,y1,y2;
    bool operator<(const BB &o)const{
        if(x1!=o.x1)return x1<o.x1;
        else if(x2!=o.x2)return x2<o.x2;
        else if(y1!=o.y1)return y1<o.y1;
        else return y2<o.y2;
    }
};
typedef vector<BB> BBV;
bool compE(E *e1,E *e2){return (e1->u!=e2->u)?(e1->u<e2->u):((e1->m!=e2->m)?e1->m<e2->m:e1->v1<e2->v1);}

/*
void prt(STM &sw){
    printf("SW: ");
    for(STMI c=sw.begin();c!=sw.end();++c)printf("[v1=%d,v2=%d,i=%d] ",c->first.v1,c->first.v2,c->second);
    printf("\n");
}
*/

bool miss(R *a,R *b){return a->x2<=b->x1||a->x1>=b->x2||a->y2<=b->y1||a->y1>=b->y2;}
bool miss(R *a,BB *b){return a->x2<=b->x1||a->x1>=b->x2||a->y2<=b->y1||a->y1>=b->y2;}
bool coll(R *a,R *b){return !miss(a,b);}
void add(STM &sw,int v1,int v2,R *rects,int i){
//    printf("add:i=%d\n",i);
    STMI e=sw.insert(make_pair(S(v1,v2),i));
    rects[i].ref=e;
//    prt(sw);
    STMI ep=e,en=e;
    if(ep!=sw.begin()){
        --ep;
        rects[ep->second].l.insert(i);
        rects[i].l.insert(ep->second);
    }
    if(++en!=sw.end()){
        rects[en->second].l.insert(i);
        rects[i].l.insert(en->second);
    }
}
void del(STM &sw,R *rects,int i){
//    printf("del:i=%d\n",i);
    sw.erase(rects[i].ref);
//    prt(sw);
}
void sweep(int m,E **pev,R *rects){
    int i;
    sort(pev,pev+m,compE);
//    for(i=0;i<m;++i) printf("%d: x=%d,y1=%d,y2=%d,m=%d\n",i,pev[i]->u,pev[i]->v1,pev[i]->v2,pev[i]->m);
    STM sw;E *ev;
    for(i=0;i<m;++i){
        ev=pev[i];
        if(ev->m<0)del(sw,rects,ev->i);
        else add(sw,ev->v1,ev->v2,rects,ev->i);
    }
}
void links(int n,R *rects){
    int m=(n<<1),i,j;
    E *ev=new E[m];E **pev=new E*[m];
    j=0;
    for(i=0;i<n;++i){
        ev[j].i=i;ev[j].u=rects[i].x1;ev[j].v1=rects[i].y1;ev[j].v2=rects[i].y2;ev[j].m=1;pev[j]=ev+j;++j;
        ev[j].i=i;ev[j].u=rects[i].x2;ev[j].v1=rects[i].y1;ev[j].v2=rects[i].y2;ev[j].m=-1;pev[j]=ev+j;++j;
    }
    sweep(m,pev,rects);
    j=0;
    for(i=0;i<n;++i){
        ev[j].i=i;ev[j].u=rects[i].y1;ev[j].v1=rects[i].x1;ev[j].v2=rects[i].x2;ev[j].m=1;pev[j]=ev+j;++j;
        ev[j].i=i;ev[j].u=rects[i].y2;ev[j].v1=rects[i].x1;ev[j].v2=rects[i].x2;ev[j].m=-1;pev[j]=ev+j;++j;
    }
    sweep(m,pev,rects);
    delete[]ev;delete[]pev;
}
void collect(int n,R *rects,BBV &bbv){
    int i;
    for(i=0;i<n;++i)if(!rects[i].u){
        for(ISI li=rects[i].l.begin();li!=rects[i].l.end();++li)if(*li!=i&&!rects[*li].u&&coll(rects+i,rects+*li)){
            rects[i].u=rects[*li].u=1;
            BB bb={min(rects[i].x1,rects[*li].x1),
                   max(rects[i].x2,rects[*li].x2),
                   min(rects[i].y1,rects[*li].y1),
                   max(rects[i].y2,rects[*li].y2)};
            IS ll;
            for(ISI t=rects[i].l.begin();t!=rects[i].l.end();++t)ll.insert(*t);
            for(ISI t=rects[*li].l.begin();t!=rects[*li].l.end();++t)ll.insert(*t);
            while(!ll.empty()){
                R *r=rects+*ll.begin();
                ll.erase(ll.begin());
                if(r->u)continue;
                if(miss(r,&bb))continue;
                r->u=1;
                if (r->x1<bb.x1)bb.x1=r->x1;
                if (r->x2>bb.x2)bb.x2=r->x2;
                if (r->y1<bb.y1)bb.y1=r->y1;
                if (r->y2>bb.y2)bb.y2=r->y2;
                for(ISI t=r->l.begin();t!=r->l.end();++t)ll.insert(*t);
            }
            bbv.push_back(bb);
            break;
        }
    }
    for(i=0;i<n;++i)if(!rects[i].u){
        BB bb={rects[i].x1,rects[i].x2,rects[i].y1,rects[i].y2};
        bbv.push_back(bb);
    }
}
int main(){
    //f_r_ e o p e n("pletest/ple6.in","r",stdin);

    int n,x1,x2,y1,y2,i,j;
    scanf("%d",&n);
    R *rects=new R[n];
    for(i=0;i<n;++i){scanf("%d%d%d%d",&x1,&x2,&y1,&y2);rects[i]=R(min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2));}
    links(n,rects);

//    printf("R: ");for(i=0;i<n;++i){printf("[i=%d,x1=%d,x2=%d,y1=%d,y2=%d,l={",i,rects[i].x1,rects[i].x2,rects[i].y1,rects[i].y2);for(ISI g=rects[i].l.begin();g!=rects[i].l.end();++g)printf("%d,",*g);printf("}], ");}printf("\n");

    BBV bbv;
    for(;;){
        collect(n,rects,bbv);
        j=(int)bbv.size();
        if(j==n)break;
        delete[]rects;
        n=j;
        rects=new R[n];
        for(i=0;i<n;++i)rects[i]=R(bbv[i].x1,bbv[i].x2,bbv[i].y1,bbv[i].y2);
        bbv.clear();
        links(n,rects);
    }
    sort(bbv.begin(),bbv.end());
    j=(int)bbv.size();
    printf("%d\n",j);
    for(i=0;i<j;++i)printf("%d %d %d %d\n",bbv[i].x1,bbv[i].x2,bbv[i].y1,bbv[i].y2);
    delete[]rects;
    return 0;
}