【集训Day3 离散化】矩形覆盖

矩形覆盖（planting）
【问题描述】
给定在一个平面坐标系上的N(1 <= N <= 100)个矩形区域，这N个矩形可能有相互覆盖的部分。求平面上被所有矩形覆盖的总面积，重复部分只算一次。
【输入格式】planting.in
第一行一个整数N。
接下来N行，每行包含4个整数x1 y1 x2 y2，表示一个矩形区域。矩形的左上角为(x1,y1)，右下角为(x2,y2)。坐标范围为–10^8到10^8之间的整数。
【输出格式】planting.out
输出被矩形覆盖的总面积。
【输入样例】
2
0 5 4 1
2 4 6 2
【输出样例】
20

【解题思路】
将输入的行和列用两个数组映射到1···n中去，将其离散化，利用另一个数组存下每一对离散的变量之间的差距
【解题反思】

解题时要注意细节

【参考程序】

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct data

{

    int num;

    int id;

}x[205],y[205];

bool comp(data a,data b)

{

    return a.num<b.num;

}

int n,bx[205],by[205],c[205][205],ans,pic[205][205];

int main()

{

    freopen("planting.in","r",stdin);

    freopen("planting.out","w",stdout);

    cin>>n;

    for (int i=1;i<=n;i++)

    {

        cin>>x[2*i-1].num>>y[2*i].num>>x[2*i].num>>y[2*i-1].num;//由于是平面直角坐标系，列轴是向上的。

        x[2*i-1].id=2*i-1;

        y[2*i-1].id=2*i-1;

        x[2*i].id=2*i;

        y[2*i].id=2*i;

    }

    sort(x+1,x+1+2*n,comp);

    sort(y+1,y+1+2*n,comp);

    for (int i=1;i<=2*n;i++)

    {

        bx[x[i].id]=i;

        by[y[i].id]=i;

    }//离散化

    for (int i=1;i<2*n;i++)

        for (int j=1;j<2*n;j++)

            c[i][j]=(x[i+1].num-x[i].num)*(y[j+1].num-y[j].num);//每一个离散的变量间的差距

    for (int i=1;i<=n;i++)

        for (int j=bx[2*i-1];j<bx[2*i];j++)

            for (int k=by[2*i-1];k<by[2*i];k++) pic[j][k]=1;//传统的标记方法，简单暴力

    for (int i=1;i<2*n;i++)

        for (int j=1;j<2*n;j++)

            if (pic[i][j]==1) ans+=c[i][j];//统计

    cout<<ans;

    return 0;

}

【集训Day3 离散化】矩形覆盖的相关教程结束。