描述

桌面上放了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。

格式

输入格式

输入第一行为一个数N（1≤N≤100），表示矩形的数量。下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–10^8到10^8之间的整数。

输出格式

输出只有一行，一个整数，表示图形的面积。

样例1

样例输入1

3
1 1 4 3
2 -1 3 2
4 0 5 2

Copy

样例输出1

10

Copy

来源

某校NOIP模拟题

题解 因为要刷一道离散化的题目，所以来搞一发离散化的题目

看了好几篇离散化的博客 我的对于离散化的理解就是很多题目数据量很大 

暴力模拟什么的算法都是很不实际的 但是我们可以将题目中的数据 通过分块分类等操作来将数据离散出来（离散相对于连续嘛）

然后题目就好解了

这个题目的解法很简单 就是将横坐标纵坐标排序

将很大的面积分成一小块一小块的 而不是原来一个点一个点那样的  

借用一下大佬图片

然后枚举出来 判断一下在不在原来的矩形里面 最后把面积加上去

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define MAXn 100
using namespace std;
int n;
long long x1[MAXn+1],y1[MAXn+1];
long long x2[MAXn+1],y2[MAXn+1];
long long x[2*MAXn+1],y[2*MAXn+1];
long long S,ans;
int main()
{
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) 
    { 
        scanf("%lld%lld%lld%lld",&x1[i],&y1[i],&x2[i],&y2[i]); 
        x[2*i-1]=x1[i]; 
        x[2*i]=x2[i]; 
        y[2*i-1]=y1[i];
        y[2*i]=y2[i]; 
    } 
    sort(x+1,x+2*n+1); 
    sort(y+1,y+2*n+1); 
    for(int i=1;i<=2*n-1;i++) //枚举每一个单位横坐标，这两句看图 
        for(int j=1;j<=2*n-1;j++)  //枚举每一个单位纵坐标
        { 
            S=(x[i+1]-x[i])*(y[j+1]-y[j]);
            for(int k=1;k<=n;k++) //枚举每一个矩形块 
                if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])//这句是离散化（判断一下小矩形块是不是在大矩形里面）
                { ans+=S; break; }//注意这个break,用的妙
        } 
    printf("%lld",ans); 
    return 0;
}

反正我写一遍也是上面这个样子，直接搬过来了这里