1 //扫描线矩形周长的并 POJ1177 2 // 我是按x轴 3  4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 #include 
         
           9 #include 
          
           10 #include 
           
            11 // #include 
            
             12 // #include 
             
              13 using namespace std;14 #define LL long long15 typedef pair
              
                pii;16 const LL inf = 0x3f3f3f3f;17 const LL MOD =100000000LL;18 const int N = 5010;19 const double eps = 1e-5;20 void fre() {freopen("in.txt","r",stdin);}21 void freout() {freopen("out.txt","w",stdout);}22 inline int read() { int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}23 24 struct node{25 int x1,x2,y;26 int flag;27 bool operator < (const node &a) const{28 return y
               
                a.flag);29 }30 }e[N<<2];31 32 int color[N<<3];33 int sum[N<<3],hashh[N<<1];34 int cnt[N<<3],pl[N<<3],pr[N<<3];35 void pushup(int rt,int l,int r){36 if(color[rt]) {37 sum[rt]=hashh[r+1]-hashh[l];38 cnt[rt]=1;39 pl[rt]=pr[rt]=1;40 }41 else if(l!=r) {42 sum[rt]=sum[rt<<1]+sum[rt<<1|1];43 cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1]-(pr[rt<<1]&&pl[rt<<1|1]);44 pr[rt]=pr[rt<<1|1];45 pl[rt]=pl[rt<<1];46 }47 else sum[rt]=cnt[rt]=pl[rt]=pr[rt]=0;48 }49 void update(int l,int r,int L,int R,int rt,int f){50 if(l<=L&&R<=r){51 color[rt]+=f;52 pushup(rt,L,R);53 return;54 }55 int mid=(L+R)>>1;56 if(l<=mid) update(l,r,L,mid,rt<<1,f);57 if(r>mid) update(l,r,mid+1,R,rt<<1|1,f);58 pushup(rt,L,R);59 }60 61 int main(){62 // fre();63 int n;64 scanf("%d",&n);65 memset(color,0,sizeof(color));66 memset(sum,0,sizeof(sum));67 memset(cnt,0,sizeof(cnt));68 memset(pr,0,sizeof(pr));69 memset(pl,0,sizeof(pl));70 int x1,x2,y1,y2;71 for(int i=1;i<=n;i++){72 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);73 e[i*2-1].x1=e[i*2].x1=x1;74 e[i*2-1].x2=e[i*2].x2=x2;75 e[i*2-1].y=y1,e[i*2].y=y2;76 e[i*2-1].flag=1,e[i*2].flag=-1;77 hashh[i*2-1]=x1,hashh[i*2]=x2;78 }79 sort(e+1,e+1+2*n);80 sort(hashh+1,hashh+1+2*n);81 int ans=0;82 int lastsum=0;83 e[0].y=e[1].y;84 for(int i=1;i<=2*n;i++){85 ans+=(e[i].y-e[i-1].y)*2*cnt[1];86 int l=lower_bound(hashh+1,hashh+1+2*n,e[i].x1)-hashh;87 int r=lower_bound(hashh+1,hashh+1+2*n,e[i].x2)-hashh-1;88 if(l<=r) update(l,r,1,2*n,1,e[i].flag);89 ans+=abs(sum[1]-lastsum);90 lastsum=sum[1]; 91 }92 printf("%d\n",ans);93 return 0;94 }