|
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 |
#pragma warning (disable:4996)#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#define maxn 150using
namespace std;int
n;struct
Segment{ double
l, r, x; int
li, ri; bool
isleft; bool
operator < (const
Segment &b) const{ return
x < b.x; }}s[maxn*3];int
top;double
ydis[800];int
ytop = 0;struct
Node{ int
cov; int
l, r; double
len;}N[3000];void
build(int
i, int
L, int
R){ N[i].cov = 0; N[i].l = L; N[i].r = R; N[i].len = ydis[R] - ydis[L]; if
(N[i].r-N[i].l<=1){ return; } int
M = (L + R) >> 1; build(i << 1, L, M); build(i << 1 | 1, M, R);}void
pushDown(int
i){ if
(N[i].r-N[i].l<=1) return; if
(N[i].cov!=0){ N[i << 1].cov += N[i].cov; N[i << 1 | 1].cov += N[i].cov; N[i].cov = 0; }}void
add(int
i, int
L, int
R,int val){ if
(N[i].l == L&&N[i].r == R){ N[i].cov += val; return; } pushDown(i); int
M = (N[i].l + N[i].r) >> 1; if
(R <= M) add(i << 1, L, R, val); else
if (L >= M) add(i << 1 | 1, L, R, val); else
{ add(i << 1, L, M, val); add(i << 1 | 1, M, R, val); }}double
query(int
i){ pushDown(i); if
(N[i].r - N[i].l <= 1&&N[i].cov>0) return
N[i].len; else
if (N[i].r - N[i].l <= 1) return
0; return
query(i << 1) + query(i << 1 | 1);}int
main(){ int
ca = 0; while
(cin >> n&&n) { double
x1, y1, x2, y2; top = 0; ytop = 0; for
(int i = 0; i < n; i++){ scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); s[top].x = x1; s[top].l = y1; s[top].r = y2; s[top++].isleft = true; s[top].x = x2; s[top].l = y1; s[top].r = y2; s[top++].isleft = false; ydis[ytop++] = y1; ydis[ytop++] = y2; } sort(ydis, ydis + ytop); ytop = unique(ydis, ydis + ytop) - ydis; sort(s, s + top); for
(int i = 0; i < top; i++){ s[i].li = lower_bound(ydis, ydis + ytop, s[i].l) - ydis; s[i].ri = lower_bound(ydis, ydis + ytop, s[i].r) - ydis; } ydis[ytop] = ydis[ytop - 1]; build(1, 0, ytop); double
ans = 0;double
lx = s[0].x; for
(int i = 0; i < top; i++){ ans += query(1)*(s[i].x - lx); if
(s[i].isleft){ add(1, s[i].li, s[i].ri ,1); } else{ add(1, s[i].li, s[i].ri, -1); } lx = s[i].x; } printf("Test case #%d\n", ++ca); printf("Total explored area: %.2lf\n", ans); puts(""); } return
0;} |
HDU1542 Atlantis(矩形面积并),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3621905.html