矩形面积

描述

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

样例输出1

第一次知道有离散化

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define LL long long
 6 using namespace std;
 7 struct node
 8 {
 9     LL x1,x2,y1,y2;
10 }a[105];
11 bool cmp(int a,int b)
12 {
13     return a<b;
14 }
15 LL x[205],y[205];
16 bool p[205][205];
17 int main()
18 {
19     long long n,ans=0,l;
20     scanf("%lld",&n);
21     for(LL i=1;i<=n;i++)
22     {
23         scanf("%lld%lld%lld%lld",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
24         x[i*2]=a[i].x1;
25         x[i*2-1]=a[i].x2;
26         y[i*2]=a[i].y1;
27         y[i*2-1]=a[i].y2;
28     }  
29     sort(x+1,x+2*n+1,cmp);
30     sort(y+1,y+2*n+1,cmp);
31     for(LL i=1;i<=n;i++)
32     for(LL X=1;X<n*2;X++)
33     {
34         if(a[i].x2<=x[X]) break;
35         if(a[i].x1>=x[X+1]) continue;
36         for(int Y=1;Y<n*2;Y++)
37         {
38             if(a[i].y2<=y[Y]) break;
39             if(a[i].y1>=y[Y+1]) continue;
40             p[X][Y]=1;
41         }
42     }
43     for(LL X=1;X<n*2;X++)
44     {
45         l=x[X+1]-x[X];
46         for(int Y=1;Y<n*2;Y++)
47         if(p[X][Y])
48         ans+=l*(y[Y+1]-y[Y]);
49     }
50     cout<<ans;
51     return 0;
52 }

View Code

以上 by dajuruo LQ_double