亚特兰蒂斯

AcWing-247-亚特兰蒂斯

分析

见《进阶指南》第219页。

实现

#include <iostream>
#include <cstring>
#include <set>
#include <unordered_map>
#include <algorithm>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

const int N = 10010;
struct boundary {
    double x, y1, y2;
    int flag;
    bool operator < (const boundary& o) const {
        return x < o.x;
    }
};
boundary a[2 * N];
set<double> s;
unordered_map<double, int> val;
double raw[2 * N];
struct node {
    int l, r;
    int cnt;
    double len;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define cnt(x) t[x].cnt
    #define len(x) t[x].len
};
node t[N << 3];

void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    cnt(rt) = len(rt) = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}
void update_len (int rt) {
    if (cnt(rt) >= 1) {
        len(rt) = raw[r(rt) + 1] - raw[l(rt)];
    } else if (l(rt) == r(rt)) {
        len(rt) = 0;
    } else {
        len(rt) = len(ls) + len(rs);
    }
}
void modify (int rt, int l, int r, int val) {
    if (l <= l(rt) && r(rt) <= r) { // 递归边界
        cnt(rt) += val;
        update_len(rt);
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    if (l <= mid) modify(ls, l, r, val);
    if (r >= mid + 1) modify(rs, l, r, val);
    update_len(rt);
}

int main () {
    int n, k = 0;
    while (cin >> n && n) {
        // ---------- 重置 ----------
        s.clear();
        val.clear();

        double x1, y1, x2, y2;
        for (int i = 1; i <= n; ++ i) {
            cin >> x1 >> y1 >> x2 >> y2;
            a[i] = { x1, y1, y2, 1 };
            a[n + i] = { x2, y1, y2, -1 };
            s.insert(y1);
            s.insert(y2);
        }

        int m = 0;
        for (auto i = s.begin(); i != s.end(); ++ i) {
            val[*i] = ++ m;
            raw[m] = *i;
        }

        build(1, 1, m - 1); // 区间 1 ~ m-1
        sort(a + 1, a + 2 * n + 1);
        double res = 0;
        for (int i = 1; i <= 2 * n - 1; ++ i) {
            boundary cur = a[i], next = a[i + 1];
            modify(1, val[cur.y1], val[cur.y2] - 1, cur.flag);
            res += (next.x - cur.x) * len(1);
        }
        printf("Test case #%d\n", ++ k);
        printf("Total explored area: %.2lf\n\n", res);
    }
    return 0;
}