poj 3695 Rectangles(직사각형 컷)

Rectangles
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 3112
 
Accepted: 864
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
제목:http://poj.org/problem?id=3695
제목: 한 평면에 직사각형을 그려서 n개의 직사각형을 줄게요. 매번 안에서 몇 개를 골라서 몇 개의 직사각형이 덮인 면적을 물어보면 질문 횟수가 많아요.
분석: 이 문제의 질문 데이터는 비교적 많지만 직사각형 수는 비교적 적고 개인적인 느낌은 직사각형으로 자르면 된다. 그래서 하나를 썼는데 1000ms가 지나갔다. 그리고 20위권은 ACRush 1위였다. 대신과 이렇게 가깝구나. 경배 중...이 문제의 또 다른 방법은 바로 선단수인데, 요즘은 너무 게을러서 쓰고 싶지 않다.
코드:

#include<cstdio>
#include<iostream>
using namespace std;
const int mm=22;
int sx[mm],sy[mm],tx[mm],ty[mm],d[mm];
int n,m,r,sum;
void Cut(int i,int ax,int ay,int bx,int by)
{
    while(i<r&&(ax>=tx[d[i]]||bx<=sx[d[i]]||ay>=ty[d[i]]||by<=sy[d[i]]))++i;
    if(i>=r)sum+=(bx-ax)*(by-ay);
    else
    {
        if(ax<sx[d[i]])Cut(i+1,ax,ay,sx[d[i]],by),ax=sx[d[i]];
        if(bx>tx[d[i]])Cut(i+1,tx[d[i]],ay,bx,by),bx=tx[d[i]];
        if(ay<sy[d[i]])Cut(i+1,ax,ay,bx,sy[d[i]]);
        if(by>ty[d[i]])Cut(i+1,ax,ty[d[i]],bx,by);
    }
}
int main()
{
    int i,cs=0,t;
    while(scanf("%d%d",&n,&m),n+m)
    {
        for(i=1;i<=n;++i)
            scanf("%d%d%d%d",&sx[i],&sy[i],&tx[i],&ty[i]);
        printf("Case %d:
",++cs);
        t=0;
        while(m--)
        {
            scanf("%d",&r);
            for(i=0;i<r;++i)
                scanf("%d",&d[i]);
            for(sum=i=0;i<r;++i)
                Cut(i+1,sx[d[i]],sy[d[i]],tx[d[i]],ty[d[i]]);
            printf("Query %d: %d
",++t,sum);
        }
        puts("");
    }
    return 0;
}