学步园

基本思想：
本题用的是离散化。
1 对读入的每个矩形的左下方与右上方的横纵坐标分别保存在数组p，q中。（也要将读入的点的坐标存在rgl[]中）

for (int i=1;i<=n;i++)<br /> {<br /> cin>>sx>>sy>>w>>h;<br /> rgl[i].sx=sx;<br /> rgl[i].sy=sy;<br /> rgl[i].ex=sx+w;<br /> rgl[i].ey=sy+h;<br /> p[i*2-1]=sx;<br /> q[i*2-1]=sy;<br /> p[i*2]=sx+w;<br /> q[i*2]=sy+h;<br /> }

2 因为p、q中的横纵坐标有重复，所以把其中的横纵不重复的放在数组x、y 中。（计算前可先升序排序）。

sort(p+1,p+2*n+1,cmp);<br /> sort(q+1,q+2*n+1,cmp);<br /> int lx=1,ly=1;<br /> int x[2*n+1],y[2*n+1];<br /> x[1]=p[1];<br /> y[1]=q[1];<br /> for (int i=2;i<=2*n;i++)<br /> {<br /> if (p[i]!=p[i-1])<br /> {<br /> lx++;<br /> x[lx]=p[i];<br /> }<br /> if (q[i]!=q[i-1])<br /> {<br /> ly++;<br /> y[ly]=q[i];<br /> }<br /> }
3 用数组val 表示原来的一个大矩形由读入的坐标所分成的每个小矩形的面积（说白了就是val[i][j]表示的是一个区域）
面积的计算： 
for (int i=1;i<lx;i++)<br /> for (int j=1;j<ly;j++)<br /> val[i][j]=(x[i+1]-x[i])*(y[j+1]-y[j]);
4 依次枚举val[i][j]的坐标是否在原先矩形的区域内，如果在就将f[i][j]置为true
bool f[2*n+2][2*n+2];<br /> memset(f,0,sizeof(f));<br /> for (int i=1;i<=n;i++)<br /> for (int xt=1;xt<lx;xt++)<br /> for (int yt=1;yt<ly;yt++)<br /> if (rgl[i].sx<=x[xt] && rgl[i].ex>=x[xt+1] && rgl[i].sy<=y[yt] && rgl[i].ey>=y[yt+1])<br /> f[xt][yt]=true;   
5 统计属于true的方格的面积和即为解.

int sum=0;<br /> for (int i=1;i<lx;i++)<br /> for (int j=1;j<ly;j++)<br /> if (f[i][j]) sum+=val[i][j]; 

关于离散化的一般介绍可以看我转的Matrix67牛的文章 http://blog.csdn.net/titikdhu/archive/2010/07/11/5726810.aspx

类似题目Sicily 1075. Input ，同样是离散化处理～

附上完整代码：

#include <iostream><br /> #include <algorithm><br /> #include <cstring><br /> using namespace std;<br /> struct retangle<br /> {<br /> int sx,sy,ex,ey;<br /> };<br /> bool cmp(int x,int y)<br /> {<br /> return x<y;<br /> }<br /> int main()<br /> {<br /> int cases;<br /> int n,sx,sy,w,h;<br /> cin>>cases;<br /> for (int o=1;o<=cases;o++)<br /> {<br /> cin>>n;<br /> retangle rgl[n+1];<br /> int val[2*n+2][2*n+2];<br /> int p[2*n+2],q[2*n+2];<br /> for (int i=1;i<=n;i++)<br /> {<br /> cin>>sx>>sy>>w>>h;<br /> rgl[i].sx=sx;<br /> rgl[i].sy=sy;<br /> rgl[i].ex=sx+w;<br /> rgl[i].ey=sy+h;<br /> p[i*2-1]=sx;<br /> q[i*2-1]=sy;<br /> p[i*2]=sx+w;<br /> q[i*2]=sy+h;<br /> }<br /> sort(p+1,p+2*n+1,cmp);<br /> sort(q+1,q+2*n+1,cmp);<br /> int lx=1,ly=1;<br /> int x[2*n+1],y[2*n+1];<br /> x[1]=p[1];<br /> y[1]=q[1];<br /> for (int i=2;i<=2*n;i++)<br /> {<br /> if (p[i]!=p[i-1])<br /> {<br /> lx++;<br /> x[lx]=p[i];<br /> }<br /> if (q[i]!=q[i-1])<br /> {<br /> ly++;<br /> y[ly]=q[i];<br /> }<br /> }<br /> for (int i=1;i<lx;i++)<br /> for (int j=1;j<ly;j++)<br /> val[i][j]=(x[i+1]-x[i])*(y[j+1]-y[j]);<br /> bool f[2*n+2][2*n+2];<br /> memset(f,0,sizeof(f));<br /> for (int i=1;i<=n;i++)<br /> for (int xt=1;xt<lx;xt++)<br /> for (int yt=1;yt<ly;yt++)<br /> if (rgl[i].sx<=x[xt] && rgl[i].ex>=x[xt+1] && rgl[i].sy<=y[yt] && rgl[i].ey>=y[yt+1])<br /> f[xt][yt]=true;<br /> int sum=0;<br /> for (int i=1;i<lx;i++)<br /> for (int j=1;j<ly;j++)<br /> if (f[i][j]) sum+=val[i][j];<br /> cout<<sum<<endl;<br /> }<br /> return 0;<br /> }<br />