[용 척 원리]hdu 2461 Rectangles

제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=2461
Rectangles
Time Limit: 5000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1268    Accepted Submission(s): 665
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.
 
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.
 
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
2008 Asia Hefei Regional Contest Online by USTC
 
Recommend
teddy   |   We have carefully selected several similar problems for you:   2462  2463  2457  2458  2456 
 
Statistic |  Submit |  Discuss |  Note
제목:
n(n<20)개의 사각형 에 m(m<=100000)개의 질문 이 있 고 각 질문 마다 주어진 사각형 의 합 면적 을 구 합 니 다.
문제 풀이 방향:
단순 용 척 원리
지정 한 사각형 과 면적 에 대해 먼저 모든 사각형 의 합 을 구하 고 두 사각형 의 교 제 를 빼 고 세 사각형 의 교 제 를 더 해서 이런 식 으로 유추 한다.
문 제 는 여러 사각형 의 교 제 를 구 하 는 것 으로 바 뀌 었 고 이것 은 두 사각형 의 교 제 를 구 하 는 것 으로 바 뀌 었 다.
코드:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 33

struct Rec
{
    int x1,y1,x2,y2;
    bool vv;
}rec[Maxn];

int n,m,num,pp[Maxn],ans;

Rec cal(Rec a,Rec b) //          
{
    Rec res;
    if(a.x1>b.x1)
        swap(a,b);

    if(b.x1>=a.x2||b.y1>=a.y2||b.y2<=a.y1)
    {
        res.vv=false;  //       0
        return res;
    }
    res.vv=true; //     true
    res.x1=b.x1;
    res.y1=max(a.y1,b.y1);

    res.x2=min(a.x2,b.x2);
    res.y2=min(a.y2,b.y2);

    return res;

}

int area(Rec cur)
{
    return (cur.x2-cur.x1)*(cur.y2-cur.y1);
}

void dfs(Rec hav,int cur,int cn)
{
    if(cur>num)
        return ;

    for(int i=cur;i<=num;i++)
    {
        Rec temp=cal(hav,rec[pp[i]]);

        if(!temp.vv)  //      
            continue;

        if(cn&1)
            ans+=area(temp); //       
        else
            ans-=area(temp);

        dfs(temp,i+1,cn^1);
    }
}
int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);

   int ca=0;

   while(scanf("%d%d",&n,&m)&&n+m)
   {
       printf("Case %d:
",++ca);

       for(int i=1;i<=n;i++)
           scanf("%d%d%d%d",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);

       for(int qu=1;qu<=m;qu++)
       {
           ans=0;

           scanf("%d",&num);
           for(int i=1;i<=num;i++)
               scanf("%d",&pp[i]);

           for(int i=1;i<=num;i++)
           {
               ans+=area(rec[pp[i]]);
               dfs(rec[pp[i]],i+1,0);

           }
           printf("Query %d: %d
",qu,ans);

       }
       putchar('
');
   }
   return 0;
}