|
问题描述
桌面上放了N个矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。(矩形的边都与坐标轴平行)
输入格式
输入第一行为一个数N（1≤N≤100），表示矩形的数量。下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为 到 之间的整数。
输出格式
输出只有一行，一个整数，表示图形的面积。
样例输入
3
1 1 4 3
2 -1 3 2
4 0 5 2
样例输出
10
【标程】 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 }