HDU 2461 Rectangles#容斥原理

http://acm.hdu.edu.cn/showproblem.php?pid=2461

題目很簡單，但是由于詢問數M可以很大，所以容易超時，這道題學到了在結構體里面寫函數的方法，這樣子效率更高，否則的話，這道題就TLE了。

?

根據容斥原理，先把每個小長方形的面積加上，然后看有沒有與該小長方形相交的，用dfs實現，當相交面積為0時，則不進行dfs，且同樣遵循奇加偶減（但代碼里因為是以第二個作為depth=1開始進行dfs的，所以是奇減偶加）。

?

AC代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;struct Node
{int x1,x2,y1,y2;Node cross(Node &R){Node tmp;tmp.x1=max(x1,R.x1);tmp.y1=max(y1,R.y1);tmp.x2=min(x2,R.x2);tmp.y2=min(y2,R.y2);return tmp;}int area(){if(x1>=x2||y1>=y2) return 0;return (x2-x1)*(y2-y1);}
}node[25];int num,r[25],ans;
void dfs(int depth,Node R,int index)
{Node tmp;for(int i=index;i<=num;i++){tmp=R.cross(node[r[i]]);if(tmp.area()){if(depth&1)ans-=tmp.area();else ans+=tmp.area();dfs(depth+1,tmp,i+1);}}
}int main()
{int n,m,cas=0;while(scanf("%d%d",&n,&m)&&n+m){cas++;for(int i=1;i<=n;i++)scanf("%d%d%d%d",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);printf("Case %d:\n",cas);for(int i=1;i<=m;i++){ans=0;scanf("%d",&num);for(int j=1;j<=num;j++)scanf("%d",&r[j]);for(int j=1;j<=num;j++){ans+=node[r[j]].area();dfs(1,node[r[j]],j+1);}printf("Query %d: %d\n",i,ans);}printf("\n");}return 0;
}