本题与《矩形面积》类似，只不过将点的个数变多，但点坐标的取值范围变小，并且每个点多了一个颜色属性而已。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103 |
#include <stdio.h>#include <algorithm>using
namespace std;const
int maxN = 1010;int n, m, a, b;int x[2*maxN], y[2*maxN], cx[2*maxN], cy[2*maxN];int *p[2*maxN];int map[2*maxN][2*maxN];int
color[maxN], ans[2501];void
input();void
process();void
compress(int
*, int
*);int
cmp(const
void *sa, const
void *sb);void
print();int
main(){ input(); compress(x,cx); compress(y,cy); process(); print(); return
0;}void
input(){ scanf("%d%d%d", &a, &b, &n); int
i; for
(i=1; i<=n; i++) { scanf("%d%d%d%d%d", &x[i], &y[i], &x[i+n], &y[i+n], &color[i]); } // 底色为白色，可以认为是一个左下角(0, 0)右上角(a, b)颜色为 1 的矩形 m = 2 * n + 1; x[0] = 0, y[0] = 0; x[m] = a, y[m] = b;}void
process(){ for
(int i=n; i>=0; i--) { int
t = i + n; for
(int j=x[i]; j<x[t]; j++) { for
(int k=y[i]; k<y[t]; k++) { if
(map[j][k]==0) map[j][k] = color[i]; } } } for
(int i=0; i<=m; i++) { for
(int j=0; j<=m; j++) { ans[map[i][j]] += cx[i] * cy[j]; } } ans[1] += ans[0];// 题目中 1 代表白色，而程序中默认初值为 0 代表白色。}void
compress(int
*x, int
*cx){ for
(int i=0; i<=m; i++) p[i] = &x[i]; qsort(p,m+1,sizeof(int*),cmp); int
t = 0, pt = *p[0]; *p[0] = t; for
(int i=1; i<=m; i++) { if
((*p[i])!=pt) { t++; cx[t-1] = *p[i] - pt; } pt = *p[i]; *p[i] = t; }}int
cmp(const
void *sa, const
void *sb){ int
a = **(int**)sa; int
b = **(int**)sb; if
(a>b) return
1; else
return -1;}void
print(){ for
(int i=1; i<2501; i++) { if
(ans[i]!=0) { printf("%d %d\n", i, ans[i]); } }} |
DGZX1563 - Shaping Regions形成的区域
原文：http://www.cnblogs.com/dgzxoi/p/3562094.html