|
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 |
#include <stdio.h>#include <algorithm>using
namespace std;int n;__int64
re;int x[200], y[200], cx[200], cy[200];int *p[200];int map[200][200];void
input();void
process();void
compress(int
*, int
*);int
cmp(const
void *sa, const
void *sb);int
main(){ input(); compress(x,cx); compress(y,cy); process(); printf("%I64d\n",re); return
0;}void
input(){ scanf("%d",&n); int
i; for
(i=0; i<n; i++) { scanf("%d%d%d%d",&x[i],&y[i],&x[i+n],&y[i+n]); }}// 模拟void
process(){ for
(int i=0; i<n; i++) { int
t = i + n; for
(int j=x[i]; j<x[t]; j++) { for
(int k=y[i]; k<y[t]; k++) { map[j][k] = 1; } } } int
z = 2 * n; for
(int i=0; i<z; i++) { for
(int j=0; j<z; j++) { if
(0==map[i][j]) continue; re += ((__int64)cx[i]) * cy[j]; } }}// 压缩坐标void
compress(int
*x, int
*cx){ 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++; 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;} |
原文：http://www.cnblogs.com/dgzxoi/p/3562061.html