POJ1151 Atlantis(扫描线入门)

前言

时隔一年,我又A了此题…(好吧上次是Pascal写的)
当然带来的是更加深刻的理解。
也发现了数据结构方面还有更多等待我去探索。

题目描述

分析

这是一道入门题,因此我尽力把过程描述得清晰些。
我们将矩形分为上下两条平行x轴的直线,用一根平行于x轴的直线,从下向上扫描。如果当前扫描到一条下面的边,那么我们对线段树维护的这个区间加都1;反之减1.同时加上当前扫描线和上一条扫描线位置的高度差乘上当前线段树中不为0的区间长度。(更好的理解可以Google看别的人画的图)
问题在于如何维护这个不为0的区间长度。
对于每个节点我们记录它所表示的线段被完全覆盖的次数,如果次数大于0,则它当前被完全覆盖,那么长度就是它维护的线段长;否则就是左儿子和右儿子的长度和(如果子节点存在的话)。
当然,根据范围,需要离散化坐标。

参考程序

调了好久的…
两个坑点:

  1. 小清新线段树的id函数l + r | l != r这里不能用,为什么呢?我实现的时候一个节点维护的都是一个线段,在递归的时候是递归这两个区间:[l, mid]和[mid, r],而不是[l, mid]和[mid + 1, r],这时候id会产生重复。(如区间[2,3]和[1,4])
  2. push_up()忘记判断没有子节点的情况,导致节点维护的len没有被更新。
typedef double real;

struct Edge {
    real lx, rx, y;     // lx, rx表示矩阵边缘的左端点和右端点,y表示线段的纵坐标
    int flag;   // 记录这是下面的边还是上面的边,下面为1(加入),上面为-1(离开)
    Edge() {}
    Edge(real lx_, real rx_, real y_, int f_) : lx(lx_), rx(rx_), y(y_), flag(f_) {}
    bool operator<(const Edge & e) const {
        return y < e.y;
    }
} E[MAXN << 1];
real X[MAXN << 1];  // 存放所有的横坐标
int N, totx, tote; 
namespace Segment_Tree {
    struct Node {
        real len;
        int flag;
    } T[MAXN << 2];
/*  突然发现应该是MAXN << 3的...结果还是AC了...
    因为最多有MAXN*2个端点,小清新的话是2倍空间,普通的话是4倍空间
    */
    int limt, QL, QR, delta;

    void _modfy(int rt, int l, int r);
    inline void init(int lim_) {
        limt = lim_;
        memset(T, 0, sizeof T);
    }
    inline void modify(int _ql, int _qr, int tg) {
        QL = _ql, QR = _qr, delta = tg;
        _modfy(1, 1, limt);
    }
    inline real cvr_len() {
        return T[1].len;
    }
}
void solve();

int main() {
    for (int k = 0; scanf("%d", &N) == 1 && N; ) {
        printf("Test case #%d\n", ++k);
        solve();
    }
    return 0;
}

void solve() {
    double x1, y1, x2, y2;
    totx = tote = 0;
    for (int i = 0; i < N; i++) {
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        E[tote++] = Edge(x1, x2, y1, 1);
        E[tote++] = Edge(x1, x2, y2, -1);
        X[++totx] = x1, X[++totx] = x2;
    }
    std::sort(E, E + tote);
    std::sort(X + 1, X + 1 + tote);
    totx = std::unique(X + 1, X + 1 + tote) - X - 1;    // 离散化
    std::map<real, int> Mp;
    for (int i = 1; i <= totx; i++) Mp[X[i]] = i;
    Segment_Tree::init(totx);
    Segment_Tree::modify(Mp[E[0].lx], Mp[E[0].rx], E[0].flag);
    real ans = 0;
    for (int i = 1; i < tote; i++) {
        ans += Segment_Tree::cvr_len() * (E[i].y - E[i - 1].y); 
        Segment_Tree::modify(Mp[E[i].lx], Mp[E[i].rx], E[i].flag);
    }
    printf("Total explored area: %.2f\n\n", ans);
}

namespace Segment_Tree {

#define lson rt << 1
#define rson rt << 1 | 1

    void push_up(int rt, int l, int r) {
        if (T[rt].flag) { T[rt].len = X[r] - X[l]; return; }
        if (r - l <= 1) { T[rt].len = 0; return; }  // 注意这里:没有被完全覆盖且没有子节点的点长度为0
        T[rt].len = T[lson].len + T[rson].len;
    }   

    void _modfy(int rt, int l, int r) {
        if (r <= QL || l >= QR) return;
        if (QL <= l && r <= QR) {
            T[rt].flag += delta;    // 更新完全覆盖的标记
            push_up(rt, l, r);
            return;
        }
        int mid = l + r >> 1;
        // 仔细思考一下会发现完全覆盖的标记无需下传,这点我想了好久
        _modfy(lson, l, mid);
        _modfy(rson, mid, r);
        push_up(rt, l, r);
    }
}

总结

通过这题,yyk告诉我线段树还有很多东西我需要学习了解的。数据结构还是毒瘤啊。对于标记的不理解也反映出对线段树本质的不清晰,我觉得这个还是要依靠多多练习把握?扫描线其实不是个很难的东西。不过想当年用Pascal写这题的时候,还是费了不少劲呢。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注