題目：Rectangles

?

題意：給N個矩形，他們可能會重疊，然后給M個詢問，每個詢問給出指定的矩形位置，然后分別計算每個詢問中選中的矩形的并。

?

本題跟求所有矩形的并一個思路，只是再增加一個數組來保存選中矩形的位置，然后直接求并即可。

#include <stdio.h> #include <string.h> #include <algorithm>using namespace std;#define LL __int64const int N = 45;typedef struct {LL x1,y1;LL x2,y2;LL sum; }Node;Node T[N];LL a[N];LL n,m,r;void Cover(LL x1,LL y1,LL x2,LL y2,LL k) {while(k<r&&(x1>=T[a[k]].x2||x2<=T[a[k]].x1||y1>=T[a[k]].y2||y2<=T[a[k]].y1)) k++;if(k>=r){T[a[k-1]].sum+=(x2-x1)*(y2-y1);return;}if(x1<T[a[k]].x1){Cover(x1,y1,T[a[k]].x1,y2,k+1);x1=T[a[k]].x1;}if(x2>T[a[k]].x2){Cover(T[a[k]].x2,y1,x2,y2,k+1);x2=T[a[k]].x2;}if(y1<T[a[k]].y1){Cover(x1,y1,x2,T[a[k]].y1,k+1);y1=T[a[k]].y1;}if(y2>T[a[k]].y2){Cover(x1,T[a[k]].y2,x2,y2,k+1);y2=T[a[k]].y2;} }int main() {LL i,tt,t=1;while(~scanf("%I64d%I64d",&n,&m)){if(n==0&&m==0) break;memset(T,0,sizeof(T));for(i=0;i<n;i++)scanf("%I64d%I64d%I64d%I64d",&T[i].x1,&T[i].y1,&T[i].x2,&T[i].y2);printf("Case %I64d:\n",t++);tt=1;while(m--){for(i=0;i<n;i++)T[i].sum=0;scanf("%I64d",&r);memset(a,0,sizeof(a));for(i=0;i<r;i++){scanf("%I64d",&a[i]);a[i]--;}for(i=r-1;i>=0;i--)Cover(T[a[i]].x1,T[a[i]].y1,T[a[i]].x2,T[a[i]].y2,i+1);LL ans=0;for(i=0;i<r;i++)ans+=T[a[i]].sum;printf("Query %I64d: ",tt++);printf("%I64d\n",ans);}puts("");}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ3695(矩形切割中等题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。