#include<iostream> #include<vector> #include<set> #include<algorithm> #define PUII std::pair<unsigned int, unsigned int> #define MSET std::multiset<PUII, std::greater<PUII > > unsigned int potega2(unsigned int n){ unsigned int i; for(i=1;i<n;i*=2); return i; } PUII first(const MSET & s){ if(s.size()>0) return *(s.begin()); else return PUII(0,0); } struct Przedzialowe{ unsigned int n; std::vector<MSET > load; std::vector<PUII > sub; Przedzialowe(unsigned int m):n(potega2(m)), load(2*n), sub(2*n,PUII(0,0)) {} void insert(unsigned int p, unsigned int k, const PUII & v, bool del=false){ p+=n,k+=n; if(del) load[p].erase(v); else load[p].insert(v); if(k!=p&&del) load[k].erase(v); else if(k!=p) load[k].insert(v); for(;p>=1;p/=2,k/=2){ if(p+1<k){ if(!(p%2)){ if(del) load[p+1].erase(v); else load[p+1].insert(v); sub[p+1]=first(load[p+1]); if(p<n) sub[p+1]=std::max(std::max(sub[p*2+2],sub[p*2+3]),sub[p+1]); } if(k%2){ if(del) load[k-1].erase(v); else load[k-1].insert(v); sub[k-1]=first(load[k-1]); if(p<n) sub[k-1]=std::max(std::max(sub[k*2-2],sub[k*2-1]),sub[k-1]); } } sub[p]=first(load[p]),sub[k]=first(load[k]); if(p<n){ sub[p]=std::max(std::max(sub[2*p],sub[2*p+1]),sub[p]); sub[k]=std::max(std::max(sub[2*k],sub[2*k+1]),sub[k]); } } } PUII query(unsigned int p, unsigned int k){ PUII r(0,0); for(p+=n,k+=n;p>=1;p/=2,k/=2){ if(p+1<k){ if(!(p%2)) r=std::max(r,sub[p+1]); if(k%2) r=std::max(r,sub[k-1]); } r=std::max(r,first(load[p])); r=std::max(r,first(load[k])); } return r; } }; struct Plemie{ Plemie():s(true) {} unsigned int x1,x2,y1,y2; bool s; void scal(const Plemie & a){ x1=std::min(x1,a.x1); y1=std::min(y1,a.y1); x2=std::max(x2,a.x2); y2=std::max(y2,a.y2); } bool operator <(const Plemie & a) const{ std::vector<unsigned int> p(4),q(4); p[0]=x1,p[1]=x2,p[2]=y1,p[3]=y2; q[0]=a.x1,q[1]=a.x2,q[2]=a.y1,q[3]=a.y2; return p<q; } }; int main(){ std::ios_base::sync_with_stdio(false); unsigned int n,m=0; std::cin>>n; std::vector<Plemie> Plemiona(n); for(unsigned int i=0;i<n;++i){ std::cin>>Plemiona[i].x1>>Plemiona[i].x2; std::cin>>Plemiona[i].y1>>Plemiona[i].y2; m=std::max(m,Plemiona[i].y2); } std::sort(Plemiona.begin(),Plemiona.end()); Przedzialowe DalszeKonce(m); PUII c; unsigned int r=n; for(unsigned int i=0;i<n;++i){ while((c=DalszeKonce.query(Plemiona[i].y1,Plemiona[i].y2-1)).first>Plemiona[i].x1){ Plemiona[i].scal(Plemiona[c.second]); Plemiona[c.second].s=false,--r; DalszeKonce.insert(Plemiona[c.second].y1,Plemiona[c.second].y2-1,c,true); } DalszeKonce.insert(Plemiona[i].y1,Plemiona[i].y2-1,PUII(Plemiona[i].x2,i)); } std::cout<<r<<"\n"; std::sort(Plemiona.begin(),Plemiona.end()); for(unsigned int i=0;i<n;++i) if(Plemiona[i].s) std::cout<<Plemiona[i].x1<<" "<<Plemiona[i].x2<<" "<<Plemiona[i].y1<<" "<<Plemiona[i].y2<<"\n"; return 0; }
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 | #include<iostream> #include<vector> #include<set> #include<algorithm> #define PUII std::pair<unsigned int, unsigned int> #define MSET std::multiset<PUII, std::greater<PUII > > unsigned int potega2(unsigned int n){ unsigned int i; for(i=1;i<n;i*=2); return i; } PUII first(const MSET & s){ if(s.size()>0) return *(s.begin()); else return PUII(0,0); } struct Przedzialowe{ unsigned int n; std::vector<MSET > load; std::vector<PUII > sub; Przedzialowe(unsigned int m):n(potega2(m)), load(2*n), sub(2*n,PUII(0,0)) {} void insert(unsigned int p, unsigned int k, const PUII & v, bool del=false){ p+=n,k+=n; if(del) load[p].erase(v); else load[p].insert(v); if(k!=p&&del) load[k].erase(v); else if(k!=p) load[k].insert(v); for(;p>=1;p/=2,k/=2){ if(p+1<k){ if(!(p%2)){ if(del) load[p+1].erase(v); else load[p+1].insert(v); sub[p+1]=first(load[p+1]); if(p<n) sub[p+1]=std::max(std::max(sub[p*2+2],sub[p*2+3]),sub[p+1]); } if(k%2){ if(del) load[k-1].erase(v); else load[k-1].insert(v); sub[k-1]=first(load[k-1]); if(p<n) sub[k-1]=std::max(std::max(sub[k*2-2],sub[k*2-1]),sub[k-1]); } } sub[p]=first(load[p]),sub[k]=first(load[k]); if(p<n){ sub[p]=std::max(std::max(sub[2*p],sub[2*p+1]),sub[p]); sub[k]=std::max(std::max(sub[2*k],sub[2*k+1]),sub[k]); } } } PUII query(unsigned int p, unsigned int k){ PUII r(0,0); for(p+=n,k+=n;p>=1;p/=2,k/=2){ if(p+1<k){ if(!(p%2)) r=std::max(r,sub[p+1]); if(k%2) r=std::max(r,sub[k-1]); } r=std::max(r,first(load[p])); r=std::max(r,first(load[k])); } return r; } }; struct Plemie{ Plemie():s(true) {} unsigned int x1,x2,y1,y2; bool s; void scal(const Plemie & a){ x1=std::min(x1,a.x1); y1=std::min(y1,a.y1); x2=std::max(x2,a.x2); y2=std::max(y2,a.y2); } bool operator <(const Plemie & a) const{ std::vector<unsigned int> p(4),q(4); p[0]=x1,p[1]=x2,p[2]=y1,p[3]=y2; q[0]=a.x1,q[1]=a.x2,q[2]=a.y1,q[3]=a.y2; return p<q; } }; int main(){ std::ios_base::sync_with_stdio(false); unsigned int n,m=0; std::cin>>n; std::vector<Plemie> Plemiona(n); for(unsigned int i=0;i<n;++i){ std::cin>>Plemiona[i].x1>>Plemiona[i].x2; std::cin>>Plemiona[i].y1>>Plemiona[i].y2; m=std::max(m,Plemiona[i].y2); } std::sort(Plemiona.begin(),Plemiona.end()); Przedzialowe DalszeKonce(m); PUII c; unsigned int r=n; for(unsigned int i=0;i<n;++i){ while((c=DalszeKonce.query(Plemiona[i].y1,Plemiona[i].y2-1)).first>Plemiona[i].x1){ Plemiona[i].scal(Plemiona[c.second]); Plemiona[c.second].s=false,--r; DalszeKonce.insert(Plemiona[c.second].y1,Plemiona[c.second].y2-1,c,true); } DalszeKonce.insert(Plemiona[i].y1,Plemiona[i].y2-1,PUII(Plemiona[i].x2,i)); } std::cout<<r<<"\n"; std::sort(Plemiona.begin(),Plemiona.end()); for(unsigned int i=0;i<n;++i) if(Plemiona[i].s) std::cout<<Plemiona[i].x1<<" "<<Plemiona[i].x2<<" "<<Plemiona[i].y1<<" "<<Plemiona[i].y2<<"\n"; return 0; } |