锐客网

  1. 首页 > 睿知 > it技术 > >

计蒜客 Overlapping Rectangles （离散化）

IT知识离散化计蒜客overlapping

知识的价值不在于占有，而在于使用。这篇文章主要讲述计蒜客 Overlapping Rectangles （离散化）相关的知识，希望能为你提供帮助。
题意：
给定一个坐标系， 给出n个矩形的左下角坐标(bx,by)和右上角坐标(tx,ty) ， 求矩形覆盖的面积， 有些区域会被多个矩形覆盖， 但只用算一次。
【计蒜客 Overlapping Rectangles （离散化）】n < = 1000,   0 < = bx,by,tx,ty < = 1e6
分析：
如果这题坐标范围很小的话， 其实可以直接开二维数组填充就好。
但因为坐标太大，无法开这样的数组，而且矩形数目不大，如果开这么大的数组很可能造成浪费，所以我们可以考虑离散化去做这题。
我觉得离散化的核心就是——用点去表示线段。
我们可以将n个矩形的2n个坐标离散化为nx个横坐标和ny纵坐标，然后排序去重。
再从新扫描这n个矩形，找出那些离散点是在这些矩形内的，就标记。 最后就可以在这最多1000*1000个点内计算出面积。
代码：

#include < iostream> #include < algorithm> #include < cstdio> #include < cstring> using namespace std; const int maxn = 2000 + 7; struct R{ int bx, by, tx, ty; }rec[maxn]; int n; int nx = 0 , ny = 0; int X[maxn], Y[maxn]; bool cover[maxn][maxn]; int solve(){ sort(X,X+nx); sort(Y,Y+ny); int ux = unique(X,X+nx) - X; //排序，去重，用点表示线段， 就是离散化的核心 int uy = unique(Y,Y+ny) - Y; //cout < < ux < < " " < < uy < < "\n"; for(int i = 0; i < n ; i++){ int tx = lower_bound(X, X+ux, rec[i].bx) - X; // 找到左下角x对应的离散化点 int ty = lower_bound(Y, Y+uy, rec[i].by) - Y; // 找到左下角y对应的离散化点for(int j = tx ; X[j] < rec[i].tx; j++){//calculate the area have covered. for(int k = ty; Y[k] < rec[i].ty; k++){ cover[j][k] = 1; //cover数组表示哪些离散化点是属于矩形内的 } } }int area = 0; for(int i = 0; i < ux; i++){ for(int j = 0; j < uy; j++){ if(cover[i][j]){ area += (X[i+1]-X[i]) * (Y[j+1]-Y[j]); } } } return area; } int main(){ //freopen("data.txt","r", stdin); while(~scanf("%d", & n)){ memset(cover,0,sizeof(cover)); nx = 0 , ny = 0; if(n == 0){ printf("*\n"); break; } for(int i = 0; i < n; i++){ scanf("%d %d %d %d", & rec[i].bx, & rec[i].by, & rec[i].tx, & rec[i].ty); X[nx++] = rec[i].bx, X[nx++] = rec[i].tx; Y[ny++] = rec[i].by, Y[ny++] = rec[i].ty; } printf("%d\n",solve()); } }

 

    推荐阅读


    上一篇：Android Framework 初探

    下一篇：Qt on Android 资源文件系统qrc与assets