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
| #include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const int MAX = 101;
struct Edge {
double x, y1, y2;
int op;
};
struct Node {
int low, up;
double len;
int cover;
};
double ally[MAX * 2];
Edge edges[MAX * 2];
Node seg[MAX << 3];
int left_child(int cur) {
return cur * 2 + 1;
}
int right_child(int cur) {
return cur * 2 + 2;
}
void push_up(int cur) {
if (seg[cur].cover > 0) {
seg[cur].len = ally[seg[cur].up] - ally[seg[cur].low];
} else if (seg[cur].up - seg[cur].low > 1) {
seg[cur].len = seg[left_child(cur)].len + seg[right_child(cur)].len;
} else {
seg[cur].len = 0;
}
}
void update(int cur, int low, int up, int op) {
if (seg[cur].low == low && seg[cur].up == up) {
seg[cur].cover += op;
} else {
if (seg[left_child(cur)].up > low) {
update(left_child(cur), low, std::min(seg[left_child(cur)].up, up), op);
}
if (seg[right_child(cur)].low < up) {
update(right_child(cur), std::max(seg[right_child(cur)].low, low), up, op);
}
}
push_up(cur);
}
void build(int cur, int low, int up) {
seg[cur] = Node { low, up, 0, 0 };
if (up - low > 1) {
int mid = (up + low) / 2;
build(left_child(cur), low, mid);
build(right_child(cur), mid, up);
}
}
int main() {
int cases = 1;
int n;
while (~scanf("%d", &n)) {
if (n == 0) {
break;
}
for (int i = 0; i < n; i++) {
double x1, y1, x2, y2;
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
edges[i * 2] = Edge { x1, y1, y2, 1 };
edges[i * 2 + 1] = Edge { x2, y1, y2, -1 };
ally[i * 2] = y1;
ally[i * 2 + 1] = y2;
}
sort(edges, edges + 2 * n, [](Edge &a, Edge &b) { return a.x < b.x; });
sort(ally, ally + 2 * n, std::less<double>());
int m = unique(ally, ally + n * 2) - ally;
build(0, 0, m - 1);
double area = 0.0;
for (int i = 0; i < n * 2; i++) {
if (i > 0) {
area += (edges[i].x - edges[i - 1].x) * seg[0].len;
}
int low = lower_bound(ally, ally + m, edges[i].y1) - ally;
int up = lower_bound(ally, ally + m, edges[i].y2) - ally;
update(0, low, up, edges[i].op);
}
printf("Test case #%d\nTotal explored area: %0.2f\n\n", cases++, area);
}
return 0;
}
|