NKOJ 1353 图形面积

时间限制 : 10000 MS 空间限制 : 65536 KB

问题描述

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

输入格式

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

输出格式

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

样例输入

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

样例输出

【标程】

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cctype>  
  4 #include<algorithm>
  5 #define ll long long
  6 #define maxn 203
  7 using namespace std;
  8 int n, tot_x, tot_y;
  9 ll ans;
 10 ll X[maxn], Y[maxn], Renew_X[maxn], Renew_Y[maxn], Map[maxn][maxn];
 11 char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
 12 bool Mark[maxn][maxn];
 13 struct node {
 14     ll x1, x2, y1, y2, xx1, xx2, yy1, yy2;
 15 }Pair[maxn];
 16 namespace Ironclad_Programming {
 17     #define R register int
 18     #define For(i, s, n) for (R i = s; i <= n; ++ i)
 19     #define Getch() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++)
 20     inline ll read() { 
 21         int x = 0, f = 1;
 22         char ch = Getch();
 23         while(!isdigit(ch)){if (ch == '-')f = -1; ch = Getch();}
 24         while(isdigit(ch))x = x * 10 + (ch ^ 48), ch = Getch(); 
 25         return x * f; 
 26     } 
 27     void write(ll x) { 
 28         if (x > 9) write(x / 10); 
 29         *O ++ = x % 10 + '0'; 
 30     }
 31     namespace ini {
 32         int j = 0;
 33         void Discretization() {
 34             Renew_X[1] = abs(X[1]);
 35             Renew_Y[1] = abs(Y[1]);
 36             For (i, 2, 2 * n) {
 37                 if (X[i] > X[i - 1]) {
 38                     Renew_X[++ tot_x] = X[i] - X[i - 1];
 39                     X[tot_x] = X[i];
 40                 }
 41                 if (Y[i] > Y[i - 1]) {
 42                     Renew_Y[++ tot_y] = Y[i] - Y[i - 1];
 43                     Y[tot_y] = Y[i];
 44                 }
 45             }
 46         }
 47         void Convert() {
 48             int j;
 49             For (i, 1, n) {
 50                 j = lower_bound(X + 1, X + tot_x, Pair[i].x1) - X;
 51                 if (X[j] == Pair[i].x1)Pair[i].xx1 = j;
 52                 j = lower_bound(X + 1, X + tot_x, Pair[i].x2) - X;
 53                 if (X[j] == Pair[i].x2)Pair[i].xx2 = j;
 54                 j = lower_bound(Y + 1, Y + tot_y, Pair[i].y1) - Y;
 55                 if (Y[j] == Pair[i].y1)Pair[i].yy1 = j;
 56                 j = lower_bound(Y + 1, Y + tot_y, Pair[i].y2) - Y;
 57                 if (Y[j] == Pair[i].y2)Pair[i].yy2 = j;
 58             }
 59         }
 60         void executive() {
 61             n = read();
 62             For (i, 1, n) {
 63                 Pair[i].x1 = read(), Pair[i].y1 = read(), Pair[i].x2 = read(), Pair[i].y2 = read();
 64                     ++ j;
 65                     X[j] = Pair[i].x1;
 66                     Y[j] = Pair[i].y1;
 67                     ++ j;
 68                     X[j] = Pair[i].x2;
 69                     Y[j] = Pair[i].y2;
 70                 }
 71                 sort(X + 1, X + 2 * n + 1);
 72                 sort(Y + 1, Y + 2 * n + 1);
 73             Discretization();
 74             Convert();
 75         }
 76     }
 77     void solve() {
 78         For (i, 1, tot_y)
 79             For (j, 1, tot_x)
 80                 Map[i][j] = Renew_Y[i] * Renew_X[j];
 81         For (i, 1, n)
 82             For (j, Pair[i].yy1 + 1, Pair[i].yy2)
 83                 For (k, Pair[i].xx1 + 1, Pair[i].xx2)
 84                     Mark[j][k] = 1;
 85         For (i, 1, tot_y)
 86             For (j, 1, tot_x)
 87                 if (Mark[i][j])
 88                     ans += Map[i][j];
 89         write(ans);
 90     }
 91     void Main() {
 92         ini::executive();
 93         solve();
 94         fwrite(obuf, O - obuf, 1, stdout);
 95     }
 96     #undef R
 97     #undef For
 98     #undef Getch
 99 }
100 int main() {
101     Ironclad_Programming::Main();
102     return 0;
103 }