离散思想的简单题目，只要掌握了离散思想，本题并不难。
首先是快排，根据排序结果压缩横坐标和纵坐标，压缩后横纵坐标的最大值不大于
200，于是就可以用模拟的方法找到结果。
|
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 |
#include <stdio.h>#include <algorithm>using
namespace std;int n, re;int x[200], y[200], c[100], tp[100];int *p[200];int map[200][200];void
input();void
process();void
compress(int
*);int
cmp(const
void *sa, const
void *sb);int
main(){ input();// 输入 compress(x);// 将 x 坐标压缩 compress(y);// 将 y 坐标压缩 process();// 模拟 printf("%d\n",re); return
0;}void
input(){ scanf("%d",&n); int
i; for
(i=0; i<n; i++) { scanf("%d%d%d%d%d",&x[i],&y[i],&x[i+n],&y[i+n],&c[i]); }}// 模拟void
process(){ int
i, j, k, t; for
(i=0; i<n; i++) { t = i + n; for
(j=x[i]; j<x[t]; j++) { for
(k=y[i]; k<y[t]; k++) { map[j][k] += c[i]; } } } t = 0; int
z = 2 * n; for
(i=0; i<z; i++) { for
(j=0; j<z; j++) { if
(0==map[i][j]) continue; bool
flag = true; for
(k=0; k<t; k++) { if
(tp[k]==map[i][j]) { flag = false; break; } } if
(flag) tp[t++] = map[i][j]; } } re = t;}// 排序的对象不是 x，而是与 x 中元素一一对应的指针数组 p。根据排序后的顺序进行压缩。void
compress(int
*x){ int
i; for
(i=0; i<2*n; i++) p[i] = &x[i]; qsort(p,2*n,sizeof(int*),cmp); int
t = 0, pt = *p[0]; *p[0] = t; for
(i=1; i<2*n; i++) { if
((*p[i])!=pt) t++; 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;} |
原文：http://www.cnblogs.com/dgzxoi/p/3562072.html