Rectangles
Time Limit: 5000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1503 Accepted Submission(s): 777
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.
Sample Input
2 2
0 0 2 2
1 1 3 3
1 1
2 1 2
2 1
0 1 1 2
2 1 3 2
2 1 2
0 0
Sample Output
Case 1:
Query 1: 4
Query 2: 7
Case 2:
Query 1: 2
Source
题意：给你n个矩形,然后m个询问,每次询问 1-n个矩形的并面积.
题解：我的方法就是每次询问的时候然后再一个个的去查询。。优化了好久,poj还是TLE hdu 1185MS水过
///离散化 #include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #include <cmath> using namespace std; const int N = 21; struct Rec { int x1,y1,x2,y2; } rec[N]; int x[N*2],y[N*2]; int vis[N*2][N*2]; int k,n,t,m; int binary1(int l,int r,int value) { int mid; while(l<r) { mid = (l+r)>>1; if(x[mid]==value) return mid; if(x[mid]<value) l = mid+1; else r = mid-1; } return l; } int binary2(int l,int r,int value) { int mid; while(l<r) { mid = (l+r)>>1; if(y[mid]==value) return mid; if(y[mid]<value) l = mid+1; else r = mid-1; } return l; } int k1,k2; void input() { k=0,t=0; int x1,y1,x2,y2; for(int i=0; i<n; i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); rec[t].x1 = x1,rec[t].y1 = y1,rec[t].x2=x2,rec[t++].y2 = y2; x[k] = x1,y[k++] = y1; x[k] = x2,y[k++] = y2; } sort(x,x+k); sort(y,y+k); k1 = 0,k2=0; x[k1] = x[0]; y[k2] = y[0]; for(int i=1;i<k;i++){ ///去重还是TLE if(x[i]!=x[i-1]) x[++k1] = x[i]; if(y[i]!=y[i-1]) y[++k2] = y[i]; } } int solve(int num) { memset(vis,0,sizeof(vis)); while(num--) { int b; scanf("%d",&b); int t1,t2,t3,t4; t1 = binary1(0,k1,rec[b-1].x1); t2 = binary1(0,k1,rec[b-1].x2); t3 = binary2(0,k2,rec[b-1].y1); t4 = binary2(0,k2,rec[b-1].y2); for(int j=t1; j<t2; j++) { for(int l = t3; l<t4; l++) { vis[j][l] = 1; } } } int area = 0; for(int i=0; i<=k1; i++) { for(int j=0; j<=k2; j++) { area+=vis[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]); } } return area; } int main() { int x1,y1,x2,y2; int cnt = 1; while(scanf("%d%d",&n,&m)!=EOF&&n+m) { input(); int a,b; printf("Case %d: ",cnt++); int cas = 1; while(m--) { scanf("%d",&a); printf("Query %d: %d ",cas++,solve(a));; } printf(" "); } return 0; }