Rectangles Area Sum

 #include<iostream>
 #include<stdio.h>
 #include<math.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;
 #define re(i,n) for(int i=0;i<n;i++)
 ;
 ;
 typedef long long ll;
 ],y[maxn*],xsz,ysz;
 struct Node{
     int fy,ty;
     int x;
     int type;
 }a[maxn*];
 bool cmp(const Node&m,const Node&n){
     return m.x<n.x;
 }
 struct Data{
     int cnt,len;
 }da[maxn*];
 int fy,ty,type;
 void insert(int id,int f,int t){
     //printf("inserting node %d ,from %d,to %d,fy %d ,ty %d,type %d\n",id,y[f],y[t],fy,ty,type);
     if(fy<=y[f]&&ty>=y[t]){
         da[id].cnt+=type;
         ){
             ;
             ].len+da[id<<|].len;
         }else da[id].len=y[t]-y[f];
         return;
     }
     ;
     |,mid,t);
     ,f,mid);
     )da[id].len=da[id<<].len+da[id<<|].len;
     else da[id].len=y[t]-y[f];
 }
 int main(){
     int n;
     while(cin>>n&&n){
         re(i,n){
             scanf(],&y[i*],&x[i*+],&y[i*+]);
             a[i*].fy=a[i*+].fy=min(y[i*],y[i*+]);
             a[i*].ty=a[i*+].ty=max(y[i*],y[i*+]);
             a[i*].x=min(x[i*],x[i*+]);
             a[i*+].x=max(x[i*],x[i*+]);
             a[i*].type=;
             a[i*+].type=-;
         }
         sort(y,y+n*),ysz=unique(y,y+n*)-y;
         sort(a,a+n*,cmp);
         ll ans=;
         memset(da,,sizeof(da));
         fy=a[].fy,ty=a[].ty,type=a[].type;
         insert(,,ysz-);
         //cout<<"The first time "<<da[1].cnt<<endl;
         //cout<<"ans is "<<ans<<endl;
         ;i<n*;i++){
             ans+=(ll)(a[i].x-a[i-].x)*da[].len;
             ans%=mod;
             fy=a[i].fy,ty=a[i].ty,type=a[i].type;
             //printf("i=%d\t ans=%lld\t ",i,ans);
             insert(,,ysz-);
         }
         cout<<ans<<endl;
     }
     ;
 }
上一篇:查看jdk的位数


下一篇:JS isArray记录