扫描线

佚名 6年前 (2019-04-12) 随笔 1686人围观抢沙发百度已收录

http://www.cnblogs.com/Konjakmoyu/p/6050343.html

关于扫描线的理解

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

https://vjudge.net/contest/242515#problem/F

Atlantis

HDU - 1542

这个题目是求总的矩形覆盖面积。线段树中的点表示的是一段区间的长度。线段按照纵坐标由小到大来更新进线段树。

线段树的结构体中有个lazy标记与长度标记，lazy标记表示这个区间段被覆盖了几次，每次只要更新相对应区间的lazy值，不需要push_down 操作，然后push_up操作是来更新长度值，如果lazy标记为1，则表示该区间

有效，如果是叶子节点就是0，如果是0就表示不能确定，只能有其左右孩子的值来确定，（这里体现为什么不需要push_down操作，因为不一定要递归到叶子节点来找长度，可以直接拿一个已经标记了的区间来表示长度，如果标记为0表示没有被标记过或者先前的1被抵消掉了（在纸上画一下），那么就要通过子节点来得到长度。）

#include<bits/stdc++.h>

using namespace std;

const int maxm = 105;
struct seg {
    double x1, x2, h;
    int fl;
//    seg(double x1 = 0, double x2 = 0, double h = 0, int fl = 0) : x1(x1), x2(x2), h(h), fl(fl) {};
    bool operator < (const struct seg &a) const {
        return h < a.h;
    }
}seg[maxm * 2];

struct Node {
    int l, r;
    int mid() {
        return (l + r) >> 1;
    }
}node[maxm << 3];
int lazy[maxm << 3];
double sum[maxm << 3];
double xx[maxm * 2];
int n;

void build(int ri, int l, int r) {
    node[ri].l = l;
    node[ri].r = r;
    lazy[ri] = 0;
    sum[ri] = 0;
    if(l == r) return;
    int m = node[ri].mid();
    build(ri << 1, l, m);
    build(ri << 1 | 1, m + 1, r);
}

void push_up(int ri) {
    if(lazy[ri]) {
        sum[ri] = xx[node[ri].r + 1] - xx[node[ri].l ];
        return;
    }
    if(node[ri].l == node[ri].r) {
        sum[ri] = 0;
        return;
    }
    sum[ri] = sum[ri << 1] + sum[ri << 1 | 1];
}

void update(int ri, int l, int r, int flag) {
    if(node[ri].l == l && node[ri].r == r) {
        lazy[ri] += flag;
        push_up(ri);
        return;
    }
    int m = node[ri].mid();
    if(r <= m) update(ri << 1, l, r, flag);
    else if(l > m) update(ri << 1 | 1, l, r, flag);
    else {
        update(ri << 1, l, m, flag);
        update(ri << 1 | 1, m + 1, r, flag);
    }
    push_up(ri);
}

int main() {
    double x1, x2, y1, y2;
    int ca = 0;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; i++) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[2 * i - 1] = (struct seg) {x1, x2, y1, 1};
            xx[2 * i - 1] = x1;
            seg[2 * i] = (struct seg) {x1, x2, y2, -1};
            xx[2 * i] = x2;
        }
        sort(seg + 1, seg + 2 * n + 1);
        sort(xx + 1, xx + 2 * n + 1);
        int k = unique(xx + 1, xx + 2 * n + 1) - xx;
        build(1, 1, k - 1);
        double res = 0;
        for(int i = 1; i < 2 * n; i++) {
            int l = lower_bound(xx + 1, xx + k, seg[i].x1) - xx;
            int r = lower_bound(xx + 1, xx + k, seg[i].x2) - xx - 1;
            if(l <= r) {
//                printf("nas\n");
                update(1, l, r, seg[i].fl);
            }
            res += sum[1] * (seg[i + 1].h - seg[i].h);
        }
//        for(int i = 1; i <= 3; i++) printf("%.2f\n", len[i]);
        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++ca, res);
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1255

求覆盖两次的矩形面积。

https://blog.csdn.net/codeswarrior/article/details/81081692 跟覆盖一次的差不多，只是结构体中长度的变为一个至少覆盖一次与至少覆盖两次的长度。

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=1082

求一个点最多是多少个矩形的交点，然后要如果一个y值有多条线，应该先让正直的先进去，然后再试负值的，保证最小。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MX = 2e4 + 5;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 0,10000,1

int MAX[MX << 2], col[MX << 2];

struct Que {
    int L, R, top, d;
    bool operator<(const Que &b)const {
        if(top == b.top) return d > b.d;
        return top < b.top;
    }
    Que(int _top = 0, int _L = 0, int _R = 0, int _d = 0) {
        L = _L; R = _R; top = _top; d = _d;
    }
} Q[MX];

void push_up(int rt) {
    MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1])+ col[rt];
}

//void push_down(int rt) {
//    if(col[rt]) {
//        col[rt << 1] += col[rt];
//        col[rt << 1 | 1] += col[rt];
//        MAX[rt << 1] += col[rt];
//        MAX[rt << 1 | 1] += col[rt];
//        col[rt] = 0;
//    }
//}

void update(int L, int R, int d, int l, int r, int rt) {
    if(L <= l && r <= R) {
        MAX[rt] += d;
        col[rt] += d;
        return;
    }

    int m = (l + r) >> 1;
//    push_down(rt);
    if(L <= m) update(L, R, d, lson);
    if(R > m) update(L, R, d, rson);
    push_up(rt);
}

int main() {
    int n;
    //freopen("input.txt", "r", stdin);
    while(~scanf("%d", &n)) {
        memset(MAX, 0, sizeof(MAX));
        memset(col, 0, sizeof(col));

        for(int i = 1; i <= n; i++) {
            int x1, x2, y1, y2;
            scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
            Q[i] = Que(y1, x1, x2, 1);
            Q[i + n] = Que(y2, x1, x2, -1);
        }
        sort(Q + 1, Q + 1 + 2 * n);

        int ans = 0;
        for(int i = 1; i <= 2 * n; i++) {
            update(Q[i].L, Q[i].R, Q[i].d, root);
            ans = max(ans, MAX[1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

https://vjudge.net/contest/285943#status/xiayuyang/N/0/

https://vjudge.net/problem/POJ-2482 天上有很多星星，求一个窗户能框住的最多的星星。

扫描线求横坐标的最小覆盖次数，因为是边框无效，所以在线段排序时让负值的排在前面，就可以保证平行于x轴方向的边框不算，然后因为线段树维护的区间是左闭右开，所以说右边界自然去掉了，

那左边界的话可以在保存x值是保存一个左边界值和一个左边界+1的值，然后在离散之后找值时找+1的那个值，在那个区间上区间加或减。

置于找最多的星星，可以用贪心的思想，枚举每一个星星，假设窗户的左下角正好在该点的左下角，然后然后查询这个区间内最多的星星数量。（有待验证）

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxm = 2e4 + 5;
ll xx[maxm << 2];
ll ma[maxm << 3], sum[maxm << 3];

struct Seg {
    ll x1, x2, h, cnt;
    bool operator < (const struct Seg &a) {
        if(h == a.h) return cnt < a.cnt;
        return h < a.h;
    }
    Seg(ll x1 = 0, ll x2 = 0, ll h = 0, ll cnt = 0) : x1(x1), x2(x2), h(h), cnt(cnt) {};
} seg[maxm << 2];

struct Node {
    int l, r;
    int mid() {
        return (l + r) >> 1;
    }
} node[maxm << 3];

void build(int ri, int l, int r) {
    node[ri].l = l;
    node[ri].r = r;
    ma[ri] = 0;
    sum[ri] = 0;
    if(l == r) return;
    int m = node[ri].mid();
    build(ri << 1, l, m);
    build(ri << 1 | 1, m + 1, r);
}

void push_up(int ri) {
    ma[ri] = max(ma[ri << 1], ma[ri << 1 | 1]) + sum[ri];
}

void update(int ri, int l, int r, int val) {
    if(node[ri].l == l && node[ri].r == r) {
        sum[ri] += val;
        ma[ri] += val;
        return;
    }
    int m = node[ri].mid();
    if(r <= m) update(ri << 1, l, r, val);
    else if(l > m) update(ri << 1 | 1, l, r, val);
    else {
        update(ri << 1, l, m, val);
        update(ri << 1 | 1, m + 1, r, val);
    }
    push_up(ri);
}


int n;
ll x, y, c, w, h;
int main() {
    while(~scanf("%d%lld%lld", &n, &w, &h)) {
        int m = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%lld%lld%lld", &x, &y, &c);
            seg[2 * i - 1] = Seg(x - 1, x + w - 1, y, c);
            seg[2 * i] = Seg(x - 1, x + w - 1, y + h, -c);
            xx[++m] = x - 1;
            xx[++m] = x;
            xx[++m] = x + w - 1;
        }
        sort(seg + 1, seg + 2 * n + 1);
        sort(xx + 1, xx + m + 1);
        int k = unique(xx + 1, xx + m + 1) - xx;
        build(1, 1, k - 1);
        ll res = 0;
        for(int i = 1; i <= 2 * n; i++) {
            int l = lower_bound(xx + 1, xx + k, seg[i].x1 + 1) - xx;
            int r = lower_bound(xx + 1, xx + k, seg[i].x2 + 1) - xx - 1;
            if(l <= r) update(1, l, r, seg[i].cnt);
            res = max(res, ma[1]);
        }
        printf("%lld\n", res);
    }
    return 0;
}