Vijos1056 图形面积

时间：2023-03-08 17:58:58
Vijos1056 图形面积

描述

桌面上放了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

样例输出1[复制] 

10

来源

某校NOIP模拟题

将所有的横线和竖线离散化排序，用它们将原矩形切分成一个个不重叠的小矩形，然后累计面积。

模拟赛的时候虽然想出了正解，但是x[]和y[]数组没有开long long，中途相乘的时候爆掉了（第二次犯错，上一次是海底高铁），只有60分

然而比赛的时候是windows评测，需要I64d，我开的是lld，如果真的开了long long，估计会爆零

……

hah……

 /*By SilverN*/

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define LL long long

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct node{

     int x1,x2,y1,y2;

 }a[mxn];

 int n;

 LL ans=;

 LL x[mxn],y[mxn];

 bool use[mxn][mxn];

 void init(){

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

         a[i].x1=read();a[i].y1=read();a[i].x2=read();a[i].y2=read();

         x[i*-]=a[i].x1;

         y[i*-]=a[i].y1;

         x[i*]=a[i].x2;

         y[i*]=a[i].y2;

     }

     sort(x+,x+n*+);

     sort(y+,y+n*+);

     return;

 }

 int main(){

     n=read();

     init();

     int i,j,k;

     int lim=n*;

     for(i=;i<=n;i++){

         for(j=;j<lim;j++){//枚举横坐标

             if(x[j]>a[i].x2)break;

             if(a[i].x1<=x[j] && x[j+]<=a[i].x2)

                 for(k=;k<lim;k++){//枚举纵坐标

                     if(y[k]>a[i].y2)break;

                     if(a[i].y1<=y[k] && y[k+]<=a[i].y2)

                         use[j][k]=;

                 }

         }

     }

     for(j=;j<lim;j++)

      for(k=;k<lim;k++){

          if(use[j][k]){

              ans+=(x[j+]-x[j])*(y[k+]-y[k]);

          }

      }

     printf("%lld\n",ans);

     return ;

 }

相关文章