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
#include<stdio.h>
#include<set>
//#include<iostream>
#include<vector>
#include<algorithm>
#define nd second
#define st first
using namespace std;
pair<int,int> zwroc_id(multiset<pair<int,int> >&S,int a,int b){
    multiset<pair<int,int> >::iterator it=S.upper_bound(make_pair(a-1,1000000));
    if(it==S.end())return make_pair(-1,-1);
    if((*it).st>b)return make_pair(-1,-1);
    //cout<<"szukam w przedziale "<<a<<" "<<b<<"\n";
    return *it;
}
void del(multiset<pair<int,int> >&S,pair<int,int>p){
    S.erase(S.find(p));
}
const int p1=1048576,p2=2097152;
multiset<pair<int,int> >drz[p2],drzy[p2];
int drz2[p2];
void wstaw(int a,int b,pair<int,int>x,multiset<pair<int,int> >*d){
	if(a+1==b)return;
	a++;
	b--;
    //cout<<"dodaj ("<<x.st<<","<<x.nd<<") na przedziale "<<a<<" "<<b<<"\n";
    a+=p1-1;
    b+=p1-1;
    d[a].insert(x);
    d[b].insert(x); 
    while((a-1)/2!=(b-1)/2){
        if(a%2==1)d[a+1].insert(x);
        if(b%2==0)d[b-1].insert(x);
        a=(a-1)/2;
        b=(b-1)/2;
    }
}
int dodaj(int a,int b,int x){
    a+=p1-1;
    b+=p1-1;
    drz2[a]+=x;
    drz2[b]+=x; 
    while((a-1)/2!=(b-1)/2){
        if(a%2==1)drz2[a+1]+=x;
        if(b%2==0)drz2[b-1]+=x;
        a=(a-1)/2;
        b=(b-1)/2;
    }
}
int suma(int a){
    a+=p1-1;
    int w=0;
    while(1){
        w+=drz2[a];
        if(a==0)break;
        a=(a-1)/2;
    }
    return w;
}
void usun(int a,int b,pair<int,int>x,multiset<pair<int,int> >*d){
	if(a+1==b)return;
	a++;
	b--;
    //cout<<"usun ("<<x.st<<","<<x.nd<<") na przedziale "<<a<<" "<<b<<"\n";
    a+=p1-1;
    b+=p1-1;
    del(d[a],x);
    del(d[b],x); 
    while((a-1)/2!=(b-1)/2){
        if(a%2==1)del(d[a+1],x);
        if(b%2==0)del(d[b-1],x); 
        a=(a-1)/2;
        b=(b-1)/2;
    }
}
pair<int,int>dowolny(int a,pair<int,int>b,multiset<pair<int,int> >*d){
    if(b.st+1==b.nd)return make_pair(-1,-1);
    b.st++;
    b.nd--;
    a+=p1-1;
    while(1){
        pair<int,int>tmp=zwroc_id(d[a],b.st,b.nd);
        if(tmp!=make_pair(-1,-1))return tmp;
        if(a==0)break;
        a=(a-1)/2;
    }
    return make_pair(-1,-1);
}
void wypisz(pair<pair<int,int>,pair<int,int> >a){
    printf("%d %d %d %d\n",a.st.st,a.st.nd,a.nd.st,a.nd.nd);
}
main(){
vector<pair<pair<int,int>,pair<int,int> > >pros,wyn;
vector<bool>jest;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
    int x1,x2,y1,y2;
    scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
    pros.push_back(make_pair(make_pair(x1,x2),make_pair(y1,y2)));
    jest.push_back(1);
    wstaw(y1,y2,make_pair(x1,i),drz);
    wstaw(y1,y2,make_pair(x2,i),drz);
    wstaw(x1,x2,make_pair(y1,i),drzy);
    wstaw(x1,x2,make_pair(y2,i),drzy);
}
for(int i=0;i<pros.size();i++){
    //wypisz(pros[i]);
    if(!jest[i]){/*cout<<"wykorzystany\n";*/continue;}
    pair<int,int>prz=dowolny(pros[i].nd.st,pros[i].st,drz);
    if(prz==make_pair(-1,-1))prz=dowolny(pros[i].nd.nd,pros[i].st,drz);
    if(prz==make_pair(-1,-1))prz=dowolny(pros[i].st.st,pros[i].nd,drzy);
    if(prz==make_pair(-1,-1))prz=dowolny(pros[i].st.nd,pros[i].nd,drzy);
    if(prz==make_pair(-1,-1)){/*cout<<"brak\n";*/continue;}
    //cout<<"jest ";
    //wypisz(pros[prz.nd]);
    usun(pros[i].nd.st,pros[i].nd.nd,make_pair(pros[i].st.st,i),drz);
    usun(pros[i].nd.st,pros[i].nd.nd,make_pair(pros[i].st.nd,i),drz);
    usun(pros[prz.nd].nd.st,pros[prz.nd].nd.nd,make_pair(pros[prz.nd].st.st,prz.nd),drz);
    usun(pros[prz.nd].nd.st,pros[prz.nd].nd.nd,make_pair(pros[prz.nd].st.nd,prz.nd),drz);
    
    usun(pros[i].st.st,pros[i].st.nd,make_pair(pros[i].nd.st,i),drzy);
    usun(pros[i].st.st,pros[i].st.nd,make_pair(pros[i].nd.nd,i),drzy);
    usun(pros[prz.nd].st.st,pros[prz.nd].st.nd,make_pair(pros[prz.nd].nd.st,prz.nd),drzy);
    usun(pros[prz.nd].st.st,pros[prz.nd].st.nd,make_pair(pros[prz.nd].nd.nd,prz.nd),drzy);
    jest[i]=0;
    jest[prz.nd]=0;
    int x1=min(pros[i].st.st,pros[prz.nd].st.st);
    int x2=max(pros[i].st.nd,pros[prz.nd].st.nd);
    int y1=min(pros[i].nd.st,pros[prz.nd].nd.st);
    int y2=max(pros[i].nd.nd,pros[prz.nd].nd.nd);
    pros.push_back(make_pair(make_pair(x1,x2),make_pair(y1,y2)));
    wstaw(y1,y2,make_pair(x1,pros.size()-1),drz);
    wstaw(y1,y2,make_pair(x2,pros.size()-1),drz);
    
    wstaw(x1,x2,make_pair(y1,pros.size()-1),drzy);
    wstaw(x1,x2,make_pair(y2,pros.size()-1),drzy);
    jest.push_back(1);
}
/*cout<<"zostaly:\n";
for(int i=0;i<pros.size();i++){
	if(!jest[i])continue;
	wypisz(pros[i]);
	pair<int,int>prz=dowolny(pros[i].nd.st,pros[i].st);
    if(prz==make_pair(-1,-1))prz=dowolny(pros[i].nd.nd,pros[i].st);
    if(prz==make_pair(-1,-1)){cout<<"brak\n";continue;}
    cout<<"jest ";
    wypisz(pros[prz.nd]);
}*/
vector<pair<pair<pair<int,int>,int>,pair<int,int> > >miot;
for(int i=0;i<pros.size();i++){
    if(!jest[i])continue;
    miot.push_back(make_pair(make_pair(make_pair(pros[i].st.st,-pros[i].st.nd),i+1),pros[i].nd));
    miot.push_back(make_pair(make_pair(make_pair(pros[i].st.nd,-1000000000),-i-1),pros[i].nd));   
}
sort(miot.begin(),miot.end());
for(int i=0;i<miot.size();i++){
    if(miot[i].st.nd<0){
        miot[i].st.nd=-miot[i].st.nd-1;
        if(!jest[miot[i].st.nd])continue;
        dodaj(miot[i].nd.st+1,miot[i].nd.nd,-1);
    }
    else{
        miot[i].st.nd--;
        if(suma(miot[i].nd.st+1)!=0){
            jest[miot[i].st.nd]=0;
            continue;
        }
        wyn.push_back(pros[miot[i].st.nd]);
        dodaj(miot[i].nd.st+1,miot[i].nd.nd,1);
    }
}
sort(wyn.begin(),wyn.end());
printf("%d\n",wyn.size());
for(int i=0;i<wyn.size();i++){
   wypisz(wyn[i]);
}
}