计蒜客 Overlapping Rectangles （离散化）

题意：

给定一个坐标系， 给出n个矩形的左下角坐标(bx,by)和右上角坐标(tx,ty) ， 求矩形覆盖的面积， 有些区域会被多个矩形覆盖， 但只用算一次。

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 =  + ;

struct R{

    int bx, by, tx, ty;

}rec[maxn];

int n;

int nx =  , ny = ;

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;//unique这个函数返回的就是去重后范围最后一个坐标，减去首地址得到去重后有多少个数值。

    for(int i = ; 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] = ; //cover数组表示哪些离散化点是属于矩形内的

            }

        }

    }

    int area = ;

    for(int i = ; i < ux; i++){

        for(int j = ; j < uy; j++){

            if(cover[i][j]){

                area += (X[i+]-X[i]) * (Y[j+]-Y[j]);

            }

        }

    }

    return area;

}

int main(){

//    freopen("data.txt","r", stdin);

    while(~scanf("%d", &n)){

        memset(cover,,sizeof(cover));

        nx =  , ny = ;

        if(n == ){

            printf("*\n");

            break;

        }

        for(int i = ; 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());

    }

}