2014
01-26

# Rectangles

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.

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 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.

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

Case 1:
Query 1: 4
Query 2: 7

Case 2:
Query 1: 2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 21
struct node
{
int c,x1,x2,y1,y2;//c表示是否重合，1重合，0不重合
}co[N],a[1<<N];
int fa[1<<N],b[N];
int f[N+10];
int c[N];
void in()
{
f[0]=1;
for(int i=1;i<=20;i++) f[i]=f[i-1]*2;
}
int zhao(int &x,int &y,int x1,int y1,int x2,int y2)
{

if(x1>x2) swap(x1,x2),swap(y1,y2);
if(x2>=y1) return 0;
else
{
x=x2;
y=MIN(y1,y2);
}
return 1;
}
void find(int t,int i,int j)
{
int c1,c2;
c1=zhao(a[t].x1,a[t].x2,a[i].x1,a[i].x2,co[j].x1,co[j].x2);
c2=zhao(a[t].y1,a[t].y2,a[i].y1,a[i].y2,co[j].y1,co[j].y2);
a[t].c=c1&c2;
j=t;
}
void init(int n)
{
int i,j;
a[0].x1=a[0].y1=0;
a[0].x2=a[0].y2=1000;
a[0].c=1;
for(i=1;i<f[n];i++) a[i].c=0;
memset(fa,0,sizeof(fa));
for(i=0;i<f[n];i++)
if(a[i].c)
{
for(j=0;j<n;j++)
if((i&f[j])==0&&fa[i+f[j]]==0)
{
fa[i+f[j]]=1;
find(i+f[j],i,j);
}
}
}
void dfs(int temp,int x,int n,int num)
{
for(int i=x;i<n;i++)
{
int j=temp+f[b[i]];
if(a[j].c)
{
c[num]+=(a[j].x2-a[j].x1)*(a[j].y2-a[j].y1);
dfs(j,i+1,n,num+1);
}
}
}
int main()
{
in();
int cases=1,n,m;
while(~scanf("%d%d",&n,&m)&&n+m)
{
int i,j,r,index;
for(i=0;i<n;i++)
scanf("%d%d%d%d",&co[i].x1,&co[i].y1,&co[i].x2,&co[i].y2);
init(n);//预处理,将所有的情况求出来
printf("Case %d:\n",cases++);
for(int k=1;k<=m;k++)
{
int sum=0;
scanf("%d",&r);
for(i=0;i<r;i++)
{
scanf("%d",&b[i]);
b[i]--;
sum+=(co[b[i]].x2-co[b[i]].x1)*(co[b[i]].y2-co[b[i]].y1);
}
memset(c,0,sizeof(c));
dfs(0,0,r,1);
int mul=-1;
for(i=2;i<=r;i++)
{
sum+=c[i]*mul;
mul*=-1;
}
printf("Query %d: %d\n",k,sum);
}
printf("\n");
}
return 0;
}

1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。