Colourful Rectangle

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 12    Accepted Submission(s): 3

Problem Description

We use Red, Green and Blue to make new colours. See the picture below:

Now give you n rectangles, the colour of them is red or green or blue. You have calculate the area of 7 different colour. (Note: A region may be covered by same colour several times, but it’s final colour depends on the kinds of different colour)

 

 

Input

The first line is an integer T(T <= 10), the number of test cases. The first line of each case contains a integer n (0 < n <= 10000), the number of rectangles. Then n lines follows. Each line start with a letter C(R means Red, G means Green, B means Blue) and four integers x1, y1, x2, y2(0 <= x1 < x2 < 10^9, 0 <= y1 < y2 < 10^9), the left-bottom's coordinate and the right-top's coordinate of a rectangle.

 

 

Output

For each case, output a line "Case a:", a is the case number starting from 1,then 7 lines, each line contain a integer, the area of each colour. (Note: You should print the areas as the order: R, G, B, RG, RB, GB, RGB).

 

 

Sample Input

3 2 R 0 0 2 2 G 1 1 3 3 3 R 0 0 4 4 G 2 0 6 4 B 0 2 6 6 3 G 2 0 3 8 G 1 0 6 1 B 4 2 7 7

 

 

Sample Output

Case 1: 3 3 0 1 0 0 0 Case 2: 4 4 12 4 4 4 4 Case 3: 0 12 15 0 0 0 0

 

 

Source

 

 

Recommend

liuyiding

 

 

 

麻烦的线段树。写了很久啊

 

//1010#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int MAXN=60010;struct Node{ int l,r; int cr,cg,cb; int lf,rf; int lr,lg,lb,lrg,lrb,lgb,lrgb; int lw;}segTree[MAXN*6];struct Line{ int x; int y1,y2; int flag; int f;}line[MAXN];int y[MAXN];bool cmp(Line a,Line b){ return a.x
            
             >1); Build(i<<1,l,mid); Build((i<<1)|1,mid,r);}void calc(int i){ if(segTree[i].l+1==segTree[i].r) { if(segTree[i].cr>0&&segTree[i].cg>0&&segTree[i].cb>0) { segTree[i].lrgb=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lg=segTree[i].lb=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=0; segTree[i].lw=0; } else if(segTree[i].cr>0&&segTree[i].cg>0) { segTree[i].lrg=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lg=segTree[i].lb=segTree[i].lrgb=segTree[i].lgb=segTree[i].lrb=0; segTree[i].lw=0; } else if(segTree[i].cr>0&&segTree[i].cb>0) { segTree[i].lrb=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lg=segTree[i].lb=segTree[i].lrgb=segTree[i].lgb=segTree[i].lrg=0; segTree[i].lw=0; } else if(segTree[i].cg>0&&segTree[i].cb>0) { segTree[i].lgb=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lg=segTree[i].lb=segTree[i].lrgb=segTree[i].lrb=segTree[i].lrg=0; segTree[i].lw=0; } else if(segTree[i].cr>0) { segTree[i].lr=segTree[i].rf-segTree[i].lf; segTree[i].lg=segTree[i].lb=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=segTree[i].lrgb=0; segTree[i].lw=0; } else if(segTree[i].cg>0) { segTree[i].lw=0; segTree[i].lg=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lb=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=segTree[i].lrgb=0; } else if(segTree[i].cb>0) { segTree[i].lb=segTree[i].rf-segTree[i].lf; segTree[i].lw=0; segTree[i].lg=segTree[i].lr=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=segTree[i].lrgb=0; } else { segTree[i].lb=0; segTree[i].lw=segTree[i].rf-segTree[i].lf; segTree[i].lg=segTree[i].lr=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=segTree[i].lrgb=0; } return; } if(segTree[i].cr>0&&segTree[i].cg>0&&segTree[i].cb>0) { segTree[i].lrgb=segTree[i].rf-segTree[i].lf; segTree[i].lr=segTree[i].lg=segTree[i].lb=segTree[i].lrg=segTree[i].lgb=segTree[i].lrb=0; segTree[i].lw=0; return; } else if(segTree[i].cr>0&&segTree[i].cg>0) { segTree[i].lr=0; segTree[i].lg=0; segTree[i].lw=0; segTree[i].lb=0; segTree[i].lrg=segTree[i<<1].lw+segTree[(i<<1)|1].lw+segTree[i<<1].lr+segTree[(i<<1)|1].lr +segTree[i<<1].lg+segTree[(i<<1)|1].lg +segTree[i<<1].lrg+segTree[(i<<1)|1].lrg; segTree[i].lrb=segTree[i].lgb=0; segTree[i].lrgb=segTree[i<<1].lb+segTree[i<<1].lrb+segTree[i<<1].lgb+segTree[i<<1].lrgb +segTree[(i<<1)|1].lb+segTree[(i<<1)|1].lrb+segTree[(i<<1)|1].lgb+segTree[(i<<1)|1].lrgb; } else if(segTree[i].cr>0&&segTree[i].cb>0) { segTree[i].lr=0; segTree[i].lg=0; segTree[i].lw=0; segTree[i].lb=0; segTree[i].lrb=segTree[i<<1].lw+segTree[(i<<1)|1].lw+segTree[i<<1].lr+segTree[(i<<1)|1].lr +segTree[i<<1].lb+segTree[(i<<1)|1].lb +segTree[i<<1].lrb+segTree[(i<<1)|1].lrb; segTree[i].lrg=segTree[i].lgb=0; segTree[i].lrgb=segTree[i<<1].lg+segTree[i<<1].lgb+segTree[i<<1].lrg+segTree[i<<1].lrgb +segTree[(i<<1)|1].lg+segTree[(i<<1)|1].lgb+segTree[(i<<1)|1].lrg+segTree[(i<<1)|1].lrgb; } else if(segTree[i].cg>0&&segTree[i].cb>0) { segTree[i].lr=0; segTree[i].lg=0; segTree[i].lw=0; segTree[i].lb=0; segTree[i].lgb=segTree[i<<1].lw+segTree[(i<<1)|1].lw+segTree[i<<1].lg+segTree[(i<<1)|1].lg +segTree[i<<1].lb+segTree[(i<<1)|1].lb +segTree[i<<1].lgb+segTree[(i<<1)|1].lgb; segTree[i].lrg=segTree[i].lrb=0; segTree[i].lrgb=segTree[i<<1].lr+segTree[i<<1].lrb+segTree[i<<1].lrg+segTree[i<<1].lrgb +segTree[(i<<1)|1].lr+segTree[(i<<1)|1].lrb+segTree[(i<<1)|1].lrg+segTree[(i<<1)|1].lrgb; } else if(segTree[i].cr>0) { segTree[i].lr=segTree[i<<1].lw+segTree[i<<1].lr +segTree[(i<<1)|1].lw+segTree[(i<<1)|1].lr; segTree[i].lw=segTree[i].lg=segTree[i].lb=0; segTree[i].lgb=0; segTree[i].lrg=segTree[i<<1].lg+segTree[i<<1].lrg +segTree[(i<<1)|1].lg+segTree[(i<<1)|1].lrg; segTree[i].lrb=segTree[i<<1].lb+segTree[i<<1].lrb +segTree[(i<<1)|1].lb+segTree[(i<<1)|1].lrb; segTree[i].lrgb=segTree[i<<1].lgb+segTree[i<<1].lrgb +segTree[(i<<1)|1].lgb+segTree[(i<<1)|1].lrgb; } else if(segTree[i].cg>0) { segTree[i].lg=segTree[i<<1].lw+segTree[i<<1].lg +segTree[(i<<1)|1].lw+segTree[(i<<1)|1].lg; segTree[i].lw=segTree[i].lr=segTree[i].lb=0; segTree[i].lrb=0; segTree[i].lrg=segTree[i<<1].lr+segTree[i<<1].lrg +segTree[(i<<1)|1].lr+segTree[(i<<1)|1].lrg; segTree[i].lgb=segTree[i<<1].lb+segTree[i<<1].lgb +segTree[(i<<1)|1].lb+segTree[(i<<1)|1].lgb; segTree[i].lrgb=segTree[i<<1].lrb+segTree[i<<1].lrgb +segTree[(i<<1)|1].lrb+segTree[(i<<1)|1].lrgb; } else if(segTree[i].cb>0) { segTree[i].lb=segTree[i<<1].lw+segTree[i<<1].lb +segTree[(i<<1)|1].lw+segTree[(i<<1)|1].lb; segTree[i].lw=segTree[i].lr=segTree[i].lg=0; segTree[i].lrg=0; segTree[i].lrb=segTree[i<<1].lr+segTree[i<<1].lrb +segTree[(i<<1)|1].lr+segTree[(i<<1)|1].lrb; segTree[i].lgb=segTree[i<<1].lg+segTree[i<<1].lgb +segTree[(i<<1)|1].lg+segTree[(i<<1)|1].lgb; segTree[i].lrgb=segTree[i<<1].lrg+segTree[i<<1].lrgb +segTree[(i<<1)|1].lrg+segTree[(i<<1)|1].lrgb; } else { segTree[i].lw=segTree[i<<1].lw+segTree[(i<<1)|1].lw; segTree[i].lr=segTree[i<<1].lr+segTree[(i<<1)|1].lr; segTree[i].lg=segTree[i<<1].lg+segTree[(i<<1)|1].lg; segTree[i].lb=segTree[i<<1].lb+segTree[(i<<1)|1].lb; segTree[i].lrg=segTree[i<<1].lrg+segTree[(i<<1)|1].lrg; segTree[i].lgb=segTree[i<<1].lgb+segTree[(i<<1)|1].lgb; segTree[i].lrb=segTree[i<<1].lrb+segTree[(i<<1)|1].lrb; segTree[i].lrgb=segTree[i<<1].lrgb+segTree[(i<<1)|1].lrgb; }}void update(int i,Line e){ if(e.y1==segTree[i].lf&&e.y2==segTree[i].rf) { if(e.flag==1) { segTree[i].cr+=e.f; } else if(e.flag==2) { segTree[i].cg+=e.f; } else if(e.flag==3) { segTree[i].cb+=e.f; } //printf("*%d %d\n",segTree[i].lf,segTree[i].rf); // printf("**%d %d %d\n",segTree[i].cr,segTree[i].cg,segTree[i].cb); calc(i); return; } if(e.y2<=segTree[i<<1].rf) update(i<<1,e); else if(e.y1>=segTree[(i<<1)|1].lf) update((i<<1)|1,e); else { Line temp=e; temp.y2=segTree[i<<1].rf; update(i<<1,temp); temp=e; temp.y1=segTree[(i<<1)|1].lf; update((i<<1)|1,temp); } calc(i);}long long out[20];int main(){ // freopen("J.in","r",stdin); // freopen("J.out","w",stdout); int x1,x2,y1,y2; char str[10]; int T; int n; scanf("%d",&T); int iCase=0; while(T--) { iCase++; scanf("%d",&n); int t=1; for(int i=1;i<=n;i++) { scanf("%s",&str); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); line[t].x=x1; line[t].y1=y1; line[t].y2=y2; line[t].f=1; if(str[0]=='R')line[t].flag=1; else if(str[0]=='G')line[t].flag=2; else line[t].flag=3; y[t]=y1; t++; line[t].x=x2; line[t].y1=y1; line[t].y2=y2; line[t].f=-1; y[t]=y2; if(str[0]=='R')line[t].flag=1; else if(str[0]=='G')line[t].flag=2; else line[t].flag=3; t++; } sort(line+1,line+t,cmp); sort(y+1,y+t); Build(1,1,t-1); memset(out,0,sizeof(out)); update(1,line[1]); for(int i=2;i