HDU 4419 다채로운 사각형 (선분 트 리)

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=4419
제목: 평면 상의 사각형 을 보 여 줍 니 다. 이 사각형 의 색깔 은 세 가지 R, G, B 가 있 습 니 다.교차 하 는 영역 은 각각 RG, RB, GB, RGB.출력 색상 은 R, G, B, RG, RB, GB, RGB 의 면적 은 각각 얼마 입 니까?
사고방식: 경 기 를 할 때 표준적 인 사각형 면적 에 비해 다양한 색깔 의 면 을 출력 해 야 한다 고 생각한다.그 당시 에 온라인 트 리 의 노드 에서 만 모든 색 채 를 기록 하고 다른 사람의 용 척 원 리 를 보고 알 수 있 었 다. 원래 이렇게 할 수 있 었 다. 위 에 7 가지 색 채 를 설치 한 면적 은 각각 1, 2, 3, 4, 5, 6, 7 이 었 다.
a = 1 + 2 + 3 + 4 + 5 + 6 + 7 (모든 사각형 을 1 회 면적 으로 구 합 니 다)
b = 1 + 2 + 4 + 5 + 6 + 7 (R 과 G 의 사각형 을 한 번 구하 기)
c = 2 + 3 + 4 = 5 + 6 + 7 (G 와 B 의 사각형 을 한 번 구하 기)
d = 1 + 3 + 4 + 5 + 6 + 7 (R 과 B 의 사각형 을 한 번 구하 기)
e = 1 + 4 + 5 + 7 (R 의 사각형 을 한 번 구하 기)
f = 2 + 4 + 6 + 7 (G 의 사각형 을 한 번 구하 기)
g = 3 + 5 + 6 + 7 (B 의 사각형 을 한 번 구하 기)
위의 7 개 식 에서 얻 을 수 있 습 니 다:
1=a-c;2=a-d;3=a-b;6=a-2-3-e;5=a-1-3-f;4=a-1-2-g;7=a-1-2-3-4-5-6;
문제 가 척척 풀리다.

 

 

 struct NODE

 {

     char color[5];

     __int64 x1,y1,x2,y2;

 };

 struct Node

 {

     __int64 L,R;

     __int64 Len; //  ,                   

     __int64 cover; //               

 

 };

 

 

 struct node

 {

     __int64 x,y1,y2;

     bool bLeft;

 

     node(){}

     node(__int64 _x,__int64 _y1,__int64 _y2,bool _bLeft)

     {

         x=_x;

         y1=_y1;

         y2=_y2;

         bLeft=_bLeft;

     }

 };

 

 const int MAX=10005;

 NODE p[MAX];

 node L[MAX*2];

 Node a[MAX*10];

 __int64 y[MAX*2];

 int n;

 

 

 bool cmp(node a,node b)

 {

     return a.x<b.x;

 }

 

 inline int DB(__int64 x)

 {

     if(x==0) return 0;

     return x>0?1:-1;

 }

 

 int find(__int64 y[],int n,__int64 val)

 {

     int low=0,high=n-1,mid;

     while(low<=high)

     {

         mid=(low+high)>>1;

         if(DB(val-y[mid])==0) return mid;

         if(DB(val-y[mid])==1) low=mid+1;

         else high=mid-1;

     }

     if(DB(val-y[0])==0) return 0;

     return n-1;

 }

 

 

 

 void insert(int t,int L,int R)

 {

     if(a[t].L==L&&a[t].R==R)

     {

         a[t].Len=y[R+1]-y[L];

         a[t].cover++;

         return;

     }

     int mid=(a[t].L+a[t].R)>>1;

     if(R<=mid) insert(t*2,L,R);

     else if(L>mid) insert(t*2+1,L,R);

     else

     {

         insert(t*2,L,mid);

         insert(t*2+1,mid+1,R);

     }

     if(a[t].cover==0) a[t].Len=a[t*2].Len+a[t*2+1].Len;

 }

 

 void del(int t,int L,int R)

 {

     if(a[t].L==L&&a[t].R==R)

     {

         a[t].cover--;

         if(a[t].cover==0)

         {

             if(a[t].L==a[t].R) a[t].Len=0;

             else a[t].Len=a[t*2].Len+a[t*2+1].Len;

         }

         return;

     }

     int mid=(a[t].L+a[t].R)>>1;

     if(R<=mid) del(t*2,L,R);

     else if(L>mid) del(t*2+1,L,R);

     else

     {

         del(t*2,L,mid);

         del(t*2+1,mid+1,R);

     }

     if(a[t].cover==0) a[t].Len=a[t*2].Len+a[t*2+1].Len;

 }

 

 void build(int t,int L,int R)

 {

     a[t].L=L;

     a[t].R=R;

     a[t].cover=0;

     a[t].Len=0;

     if(L==R) return;

     int mid=(L+R)>>1;

     build(t*2,L,mid);

     build(t*2+1,mid+1,R);

 }

 



 __int64 cal_cross_area(NODE p[],int n)

 {

     if(!n) return 0;

     int i,k;

     __int64 x1,y1,x2,y2;

     for(i=0;i<n;i++)

     {

         x1=p[i].x1;

         y1=p[i].y1;

         x2=p[i].x2;

         y2=p[i].y2;

         y[i*2]=y1;

         y[i*2+1]=y2;

         L[i*2]=node(x1,y1,y2,true);

         L[i*2+1]=node(x2,y1,y2,false);

     }

     sort(y,y+2*n);

     sort(L,L+2*n,cmp);

     k=unique(y,y+2*n)-y;

     build(1,0,k-2);

     __int64 ans=0;

     for(i=0;i<2*n-1;i++)

     {

         int left=find(y,k,L[i].y1) ;

         int right=find(y,k,L[i].y2) ;

         if(L[i].bLeft) insert(1,left,right-1);

         else del(1,left,right-1);

         ans+=((__int64)a[1].Len)*(L[i+1].x-L[i].x);

     }

     return ans;

 }

 

 int C,num=0;

 

 int main()

 {

     for(scanf("%d",&C);C--;)

     {

         scanf("%d",&n);

         int i;

         __int64 x1,y1,x2,y2;

         for(i=0;i<n;i++)

         {

             scanf("%s%I64d%I64d%I64d%I64d",p[i].color,&x1,&y1,&x2,&y2);

             p[i].x1=x1;

             p[i].y1=y1;

             p[i].x2=x2;

             p[i].y2=y2;

         }

         __int64 a,b,c,d,e,f,g;

 

         a=cal_cross_area(p,n);

         NODE Q[MAX];

         int N;

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='R'||p[i].color[0]=='G')

            Q[N++]=p[i];

         b=cal_cross_area(Q,N);

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='B'||p[i].color[0]=='G')

            Q[N++]=p[i];

         c=cal_cross_area(Q,N);

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='R'||p[i].color[0]=='B')

            Q[N++]=p[i];

         d=cal_cross_area(Q,N);

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='R')

            Q[N++]=p[i];

         e=cal_cross_area(Q,N);

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='G')

            Q[N++]=p[i];

         f=cal_cross_area(Q,N);

 

         N=0;

         for(i=0;i<n;i++) if(p[i].color[0]=='B')

            Q[N++]=p[i];

         g=cal_cross_area(Q,N);

 

         __int64 _1,_2,_3,_4,_5,_6,_7;

         _1=a-c;

         _2=a-d;

         _3=a-b;

         _6=a-_2-_3-e;

         _5=a-_1-_3-f;

         _4=a-_1-_2-g;

         _7=a-_1-_2-_3-_4-_5-_6;

 

         printf("Case %d:
",++num);

         printf("%I64d
%I64d
%I64d
%I64d
%I64d
%I64d
%I64d
",_1,_2,_3,_4,_5,_6,_7);

     }

     return 0;

 }