记录编号	575827	评测结果	AAAAAAAAAA
题目名称	[POJ 1151]亚特兰蒂斯	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	2.204 s
提交时间	2022-09-28 20:27:52	内存使用	6.18 MiB

#include <bits/stdc++.h>

struct Seg {
    int f;
    double l, r, h;
    Seg () { }
    Seg (double l, double r, double h, int f) : l(l), r(r), h(h), f(f) { }

    bool operator < (Seg& rst) { return h < rst.h; }
};

struct P {
    int cnt; double len;
};

const int N = 20010;
Seg e[N];
P t[N * 4];
double X[N];

void pushdown(int l, int r, int root) {
    if (t[root].cnt)
        t[root].len = X[r + 1] - X[l];
    else if (l == r)
        t[root].len = 0;
    else 
        t[root].len = t[root * 2].len + t[root * 2 + 1].len;
}

void update(int L, int R, int l, int r, int root, int val) {
    if (L <= l && r <= R) {
        t[root].cnt += val;
        pushdown(l, r, root);
        return;
    }
    int mid = l + r >> 1;
    if (L <= mid) update(L, R, l, mid, root * 2, val);
    if (R > mid) update(L, R, mid + 1, r, root * 2 + 1, val);
    pushdown(l, r, root);
}

int main() {
    freopen("atlantis.in", "r", stdin); 
    freopen("atlantis.out", "w", stdout);
    int n, q = 1;
    double a, b, c, d;
    while (std::cin >> n, n) {
        memset(t, 0, sizeof t);
        int cnt = 0;
        for (int i = 0; i < n; ++ i) {
            std::cin >> a >> b >> c >> d;
            X[cnt] = a, e[cnt ++] = Seg (a, c, b, 1);
            X[cnt] = c, e[cnt ++] = Seg (a, c, d, -1);
        }
        std::sort(X, X + cnt),
        std::sort(e, e + cnt);
        int all = std::unique(X, X + cnt) - X;
        double ans = 0;
        for (int i = 0; i < cnt; ++ i) {
            int l = std::lower_bound(X, X + all, e[i].l) - X;
            int r = std::lower_bound(X, X + all, e[i].r) - X - 1;
            update(l, r, 0, all, 1, e[i].f);
            ans += t[1].len * (e[i + 1].h - e[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", q ++, ans);
    }
    return 0;
}