HDU1542--Atlantis(扫描线)

给N个矩形的端点坐标，求矩形覆盖面积和。

原理很简单，从左到右扫描，线段树记录的是纵向覆盖的长度。区间更新。因为坐标是实数而且很大，所以需要离散化。

WA+RE+CE+MLE+。。。一共错了二十多次。用了最蠢的办法，最后发现错在初始化的时候，构造函数参数我写成了int。。蠢哭。。。

和普通的线段树是不同的，因为此类题型中矩形左右两竖边的长度时相同的，而且每次都是先加一在减一，不会出现负数。而且最后用到的只有总长度。

AC代码：

#include <bits/stdc++.h>

#define clr(x,c) memset(x,c,sizeof(x))

using namespace std;

const int N = 20005;

struct ScanLine {

    double x;

    double upY, downY;

    int flag;   // 入边1 出边-1

    bool operator<(const ScanLine a) const {

        return x < a.x;

    }

    ScanLine() {}

    ScanLine(double x, double y1, double y2, int f) : x(x), upY(y1), downY(y2), flag(f) {}

} line[N];

double tr[N];

int cover[N];

double yy[N];

#define lson (o<<1)

#define rson (o<<1|1)

#define mid (l+r>>1)

int yl, yr, v;

void pushup(int o, int l, int r)

{

    if (cover[o]) tr[o] = yy[r] - yy[l];

    else if (l + 1 == r) tr[o] = 0;         // 叶子

    else tr[o] = tr[lson] + tr[rson];

}

void update(int o, int l, int r)

{

    if (yl > r || yr < l) return ;

    if (yl <= l && yr >= r) {

        cover[o] += v;

        pushup(o, l, r);

        return ;

    }

    if (l + 1 == r) return ;                // 不包含的叶子节点要退出，否则死循环T^T

    if (yl <= mid) update(lson, l, mid);

    if (yr > mid) update(rson, mid, r);     // 注意这里不是mid+1 因为mid~mid+1一段的距离也要算

    pushup(o, l ,r);

}

int main()

{

    int n;

    int cas = 0;

    while (~scanf("%d", &n) && n) {

        int cnt = 0;

        double x1, y1, x2, y2;

        for (int i = 0; i < n; ++i) {

            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

            line[++cnt] = ScanLine(x1, y2, y1, 1);

            yy[cnt] = y1;

            line[++cnt] = ScanLine(x2, y2, y1, -1);

            yy[cnt] = y2;

        }

        sort(yy + 1, yy + cnt + 1);

        sort(line + 1, line + cnt + 1);

        int len = unique(yy + 1, yy + cnt + 1) - yy - 1;

        clr(cover, 0);

        clr(tr, 0);

        double ans = 0;

        for (int i = 1; i <= cnt; ++i) {

            ans += tr[1] * (line[i].x - line[i - 1].x);

            yl = lower_bound(yy+1, yy + len + 1, line[i].downY) - yy;

            yr = lower_bound(yy+1, yy + len + 1, line[i].upY) - yy;

            v = line[i].flag;

            update(1, 1, len);

        }

        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++cas, ans);

    }

	return 0;

}

还有一种方法，比较好理解，和平时的线段树比较像，就是对于每个区间求[l, r-1]，算的时候右边加一，这样递归的时候就不用考虑叶子节点了。

#include <bits/stdc++.h>

#define clr(x,c) memset(x,c,sizeof(x))

using namespace std;

const int N = 20005;

struct ScanLine {

    double x;

    double upY, downY;

    int flag;   // 入边1 出边-1

    bool operator<(const ScanLine a) const {

        return x < a.x;

    }

    ScanLine() {}

    ScanLine(double x, double y1, double y2, int f) : x(x), upY(y1), downY(y2), flag(f) {}

} line[N];

double tr[N];

int cover[N];

double yy[N];

#define lson (o<<1)

#define rson (o<<1|1)

#define mid ((l+r)>>1)

int yl, yr, v;

void pushup(int o, int l, int r)

{

    if (cover[o] > 0) tr[o] = yy[r+1] - yy[l];

    else if (l == r) tr[o] = 0;

    else tr[o] = tr[lson] + tr[rson];

}

void update(int o, int l, int r)

{

    if (yl > r || yr < l) return ;

    if (yl <= l && yr >= r) {

        cover[o] += v;

        pushup(o, l, r);

        return ;

    }

    if (yl <= mid) update(lson, l, mid);

    if (yr > mid) update(rson, mid + 1, r);

    pushup(o, l ,r);

}

int main()

{

    int n;

    int cas = 0;

    while (~scanf("%d", &n) && n) {

        int cnt = 0;

        double x1, y1, x2, y2;

        for (int i = 0; i < n; ++i) {

            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

            line[++cnt] = ScanLine(x1, y2, y1, 1);

            yy[cnt] = y1;

            line[++cnt] = ScanLine(x2, y2, y1, -1);

            yy[cnt] = y2;

        }

        sort(yy + 1, yy + cnt + 1);

        sort(line + 1, line + cnt + 1);

        int len = unique(yy + 1, yy + cnt + 1) - yy - 1;

        clr(cover, 0);

        clr(tr, 0);

        double ans = 0;

        for (int i = 1; i <= cnt; ++i) {

            ans += tr[1] * (line[i].x - line[i - 1].x);

            yl = lower_bound(yy+1, yy+len+1, line[i].downY) - yy;

            yr = lower_bound(yy+1, yy+len+1, line[i].upY) - yy - 1;

            v = line[i].flag;

            update(1, 1, len-1);

        }

        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++cas, ans);

    }

	return 0;

}

巴特西

HDU1542--Atlantis(扫描线)

最新文章

热门文章