POJ 1151 Atlantis

Posted on Edited on In 
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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 101;
int n, k, tot;
double ans, x1, y1, x2, y2;
struct Line {
    double x, y1, y2;
    int d;
    bool operator < (const Line &o) const {
        return x < o.x; // scan from left to right.
    }
} line[N << 1];
struct Node {
    int l, r, cnt; // left, right, count of covered times.
    double len; // length/height of covered range.
} tr[N << 3];
double ys[N << 1];
int get(double x) {
    return lower_bound(ys + 1, ys + 1 + tot, x) - ys;
}
// pushup to the root to make sure len is maintained properly.
void pushup(int u) {
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r) {
        // (u << 1) when tr[u].t == tr[u].r (leaf node) could cause segfault.
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    } else tr[u].len = 0;
}
// no need to pushup on building coz all cnt/len is 0.
void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0};
    if (l != r) {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}
// the query is against the whole tree every time,
// and update for every single range is paired and comes with +d first, -d next.
// so no need to push down.
void update(int u, int l, int r, int d) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].cnt += d;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
    }
    pushup(u);
}
int main() {
    while (scanf("%d", &n), n) {
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            line[i] = {x1, y1, y2, 1}, line[i + n] = {x2, y1, y2, -1};
            ys[i] = y1, ys[i + n] = y2;
        }
        n *= 2; // for convenience.
        sort(ys + 1, ys + 1 + n);
        tot = unique(ys + 1, ys + 1 + n) - ys - 1;
        build(1, 1, tot - 1);
        sort(line + 1, line + 1 + n);
        update(1, get(line[1].y1), get(line[1].y2) - 1, line[1].d);
        for (int i = 2; i <= n; ++i) {
            ans += tr[1].len * (line[i].x - line[i - 1].x);
            update(1, get(line[i].y1), get(line[i].y2) - 1, line[i].d);
        }
        printf("Test case #%d\n", ++k);
        printf("Total explored area: %.2f\n\n", ans);
    }
    return 0;
}