Rectangles
Time Limit: 5000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1497 Accepted Submission(s): 773
Problem Description
You
are developing a software for painting rectangles on the screen. The
software supports drawing several rectangles and filling some of them
with a color different from the color of the background. You are to
implement an important function. The function answer such queries as
what is the colored area if a subset of rectangles on the screen are
filled.
Input
The
input consists of multiple test cases. Each test case starts with a
line containing two integers N(1 ≤ N ≤ 20) and M(1 ≤ M ≤ 100000),
indicating the number of rectangles on the screen and the number of
queries, respectively.
The i-th line of the following N lines contains four integers X1,Y1,X2,Y2 (0 ≤ X1 < X2 ≤ 1000, 0 ≤ Y1 < Y2 ≤ 1000), which indicate that the lower-left and upper-right coordinates of the i-th rectangle are (X1, Y1) and (X2, Y2). Rectangles are numbered from 1 to N.
The last M lines of each test case describe M queries. Each query starts with a integer R(1<=R ≤ N), which is the number of rectangles the query is supposed to fill. The following list of R integers in the same line gives the rectangles the query is supposed to fill, each integer of which will be between 1 and N, inclusive.
The last test case is followed by a line containing two zeros.
The i-th line of the following N lines contains four integers X1,Y1,X2,Y2 (0 ≤ X1 < X2 ≤ 1000, 0 ≤ Y1 < Y2 ≤ 1000), which indicate that the lower-left and upper-right coordinates of the i-th rectangle are (X1, Y1) and (X2, Y2). Rectangles are numbered from 1 to N.
The last M lines of each test case describe M queries. Each query starts with a integer R(1<=R ≤ N), which is the number of rectangles the query is supposed to fill. The following list of R integers in the same line gives the rectangles the query is supposed to fill, each integer of which will be between 1 and N, inclusive.
The last test case is followed by a line containing two zeros.
Output
For each test case, print a line containing the test case number( beginning with 1).
For each query in the input, print a line containing the query number (beginning with 1) followed by the corresponding answer for the query. Print a blank line after the output for each test case.
For each query in the input, print a line containing the query number (beginning with 1) followed by the corresponding answer for the query. Print a blank line after the output for each test case.
思路：容斥原理；
感觉这题的数据有点水，按照这个复杂度O（2^n*m）是 感觉会超时的；
跑了1200多Ms。
思路很简单，就是容斥求面积。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<stack> 7 #include<map> 8 using namespace std; 9 typedef struct pp 10 { 11 int x1; 12 int y1; 13 int x2; 14 int y2; 15 } ss; 16 ss ju[30]; 17 int quer[1<<22]; 18 int cnt[30]; 19 int aa[1<<22]; 20 int bt[30]; 21 int cp[100005]; 22 int ask[100005]; 23 int tt[100]; 24 int N; 25 void dfs(int k,int u); 26 int main(void) 27 { 28 int i,j,k,p,q; 29 int kk=0; 30 while(scanf("%d %d",&p,&q),p!=0&&q!=0) 31 { 32 kk++; 33 memset(ask,0,sizeof(ask)); 34 for(i=0; i<p; i++) 35 { 36 scanf("%d %d %d %d",&ju[i].x1,&ju[i].y1,&ju[i].x2,&ju[i].y2); 37 } 38 int s; 39 int n; 40 for(s=0; s<q; s++) 41 { 42 N=0; 43 scanf("%d",&n); 44 int mn=0; 45 int dd; 46 for(i=0; i<n; i++) 47 { 48 scanf("%d",&dd); 49 mn|=(1<<(dd-1)); 50 } 51 cp[s]=mn; 52 } 53 int flag[23]; 54 for(i=1; i<=(1<<p)-1; i++) 55 { 56 int cn=0; 57 memset(flag,0,sizeof(flag)); 58 for(j=0; j<p; j++) 59 { 60 if(i&(1<<j)) 61 { 62 cn++; 63 flag[j]=1; 64 } 65 } 66 int nn; 67 int ak=0; 68 for(nn=0; nn<22; nn++) 69 { 70 if(flag[nn]) 71 { 72 cnt[ak++]=nn; 73 } 74 } 75 int mm; 76 int xx1,yy1,xx2,yy2; 77 xx1=ju[cnt[0]].x1; 78 yy1=ju[cnt[0]].y1; 79 xx2=ju[cnt[0]].x2; 80 yy2=ju[cnt[0]].y2; 81 int uu=0; 82 for(nn=1; nn<ak; nn++) 83 { 84 if(xx1>=ju[cnt[nn]].x2) 85 { 86 uu=1; 87 aa[i]=0; 88 break; 89 } 90 else if(xx2<=ju[cnt[nn]].x1) 91 { 92 uu=1; 93 aa[i]=0; 94 break; 95 } 96 else if(yy1>=ju[cnt[nn]].y2) 97 { 98 uu=1; 99 aa[i]=0; 100 break; 101 } 102 else if(yy2<=ju[cnt[nn]].y1) 103 { 104 uu=1; 105 aa[i]=0; 106 break; 107 } 108 else 109 { 110 xx1=max(xx1,ju[cnt[nn]].x1); 111 yy1=max(yy1,ju[cnt[nn]].y1); 112 xx2=min(xx2,ju[cnt[nn]].x2); 113 yy2=min(yy2,ju[cnt[nn]].y2); 114 } 115 } 116 if(!uu) 117 { 118 int miji=abs(xx1-xx2)*abs(yy1-yy2); 119 aa[i]=miji; 120 for(s=0; s<q; s++) 121 { 122 int gg=cp[s]|i; 123 if(gg<=cp[s]) 124 { 125 if(cn%2) 126 { 127 ask[s]+=aa[i]; 128 } 129 else ask[s]-=aa[i]; 130 } 131 } 132 } 133 } 134 printf("Case %d: ",kk); 135 for(j=0; j<q; j++) 136 { 137 printf("Query %d: ",j+1); 138 printf("%d ",ask[j]); 139 } 140 printf(" "); 141 } 142 return 0; 143 }