天天看點
傳回

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

HDU 1542 [POJ 1151] Atlantis （矩形面積并）

  • 題意:
    求N<=100個矩形的面積并
  • 分析:
    • 離散化: 這些技巧都是老生常談的了, 不然浮點數怎麼建樹, 離散化 x 坐标就可以了

    • 掃描線: 首先把矩形按y軸分成兩條邊, 上邊和下邊, 對 x 軸建樹, 掃描線可以看成一根平行于x軸的直線.

      從 y=0 開始往上掃, 下邊表示要計算面積 +1 , 上邊表示已經掃過了 −1 , 直到掃到最後一條平行于 x 軸的邊

      但是真正在做的時候, 不需要完全模拟這個過程, 一條一條邊地插入線段樹就好了

    • 線段樹: 用于動态維護掃描線在往上走時, x軸哪些區域是有合法面積的
    • ps: 這種線段樹是不用 lazy 的, 因為不用 push_down , 為啥不用 push_down , 因為沒有查詢操作
  • 掃描線掃描的過程（建議配合代碼模拟）

    ps:無論說的再好,都不如自己在紙上模拟一遍掃描的過程,我自己學的時候模拟了很多遍

    以下圖轉載自@kk303的部落格

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

初始狀态

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

掃到最下邊的線, 點 1→3 更新為 1

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

掃到第二根線, 此時S=lcnt!=0∗h兩根線之間, 得到綠色的面積, 加到答案中去, 随後更新計數

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

同上, 将黃色的面積加到答案中去

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

同上, 将灰色的面積加到答案中去

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

同上, 将紫色的面積加到答案中去

矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）

同上, 将藍色的面積加到答案中去

  • 代碼 
//
//  Created by TaoSama on 2015-07-14
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = , INF = , MOD =  + ;

int n;
struct Seg {
    double l, r, h; int d;
    Seg() {}
    Seg(double l, double r, double h, int d): l(l), r(r), h(h), d(d) {}
    bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[N];

int cnt[N << ]; //根節點維護的是[l, r+1]的區間
double sum[N << ], all[N];

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

void push_up(int l, int r, int rt) {
    if(cnt[rt]) sum[rt] = all[r + ] - all[l];
    else if(l == r) sum[rt] = ; //leaves have no sons
    else sum[rt] = sum[rt << ] + sum[rt <<  | ];
}

void update(int L, int R, int v, int l, int r, int rt) {
    if(L <= l && r <= R) {
        cnt[rt] += v;
        push_up(l, r, rt);
        return;
    }
    int m = l + r >> ;
    if(L <= m) update(L, R, v, lson);
    if(R > m) update(L, R, v, rson);
    push_up(l, r, rt);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    int kase = ;
    while(scanf("%d", &n) ==  && n) {
        for(int i = ; i <= n; ++i) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            a[i] = Seg(x1, x2, y1, );
            a[i + n] = Seg(x1, x2, y2, -);
            all[i] = x1; all[i + n] = x2;
        }
        n <<= ;
        sort(a + , a +  + n);
        sort(all + , all +  + n);
        int m = unique(all + , all +  + n) - all - ;

        memset(cnt, , sizeof cnt);
        memset(sum, , sizeof sum);

        double ans = ;
        for(int i = ; i < n; ++i) {
            int l = lower_bound(all + , all +  + m, a[i].l) - all;
            int r = lower_bound(all + , all +  + m, a[i].r) - all;
            if(l < r) update(l, r - , a[i].d, , m, );
            ans += sum[] * (a[i + ].h - a[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kase, ans);
    }
    return ;
}

HDU 1255 覆寫的面積 （矩形面積交）

  • 題意:
    求N<=1000個矩形覆寫至少兩次區域的面積,也就是矩形面積交
  • 分析

    • 前面的與矩形面積并類似, 不同的是 push_up 的時候要考慮至少覆寫一次 one 和至少覆寫兩次 two 的更新

      尤其是目前被覆寫了一次的時候, 由于沒有 push_down 操作, 父親節點的資訊是沒有同步到兒子節點的, 這樣的話 push_up 就要考慮了.

    • 父親被記錄覆寫了一次, 但是如果兒子被覆寫過, 這些操作都是在這個父親這個大區間上的, 就相當于父親區間被覆寫了至少兩次, 是以 two 和 one 都要更新
  • 代碼 
//
//  Created by TaoSama on 2015-10-04
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

int n;
struct Seg {
    double l, r, h; int d;
    Seg() {}
    Seg(double l, double r, double h, double d): l(l), r(r), h(h), d(d) {}
    bool operator< (const Seg& rhs) const {
        return h < rhs.h;
    }
} a[N];

int cnt[N << ];
double one[N << ], two[N << ], all[N];

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

void push_up(int l, int r, int rt) {
    if(cnt[rt] >= ) two[rt] = one[rt] = all[r + ] - all[l];
    else if(cnt[rt] == ) {
        one[rt] = all[r + ] - all[l];
        if(l == r) two[rt] = ;
        else two[rt] = one[rt << ] + one[rt <<  | ];
    } else {
        if(l == r) one[rt] = two[rt] = ;
        else {
            one[rt] = one[rt << ] + one[rt <<  | ];
            two[rt] = two[rt << ] + two[rt <<  | ];
        }
    }
}

void update(int L, int R, int v, int l, int r, int rt) {
    if(L <= l && r <= R) {
        cnt[rt] += v;
        push_up(l, r, rt);
        return;
    }
    int m = l + r >> ;
    if(L <= m) update(L, R, v, lson);
    if(R > m) update(L, R, v, rson);
    push_up(l, r, rt);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = ; i <= n; ++i) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            a[i] = Seg(x1, x2, y1, );
            a[i + n] = Seg(x1, x2, y2, -);
            all[i] = x1; all[i + n] = x2;
        }
        n <<= ;
        sort(a + , a +  + n);
        sort(all + , all +  + n);
        int m = unique(all + , all +  + n) - all - ;

        memset(cnt, , sizeof cnt);
        memset(one, , sizeof one);
        memset(two, , sizeof two);

        double ans = ;
        for(int i = ; i < n; ++i) {
            int l = lower_bound(all + , all +  + m, a[i].l) - all;
            int r = lower_bound(all + , all +  + m, a[i].r) - all;
            if(l < r) update(l, r - , a[i].d, , m, );
            ans += two[] * (a[i + ].h - a[i].h);
        }
        printf("%.2f\n", ans);
    }
    return ;
}

HDU 1828 [POJ 1177] Picture（矩形周長并）

  • 題意:
    求N<=5000個矩形的輪廓長度,也就是矩形周長并
  • 分析一:

    可以用類似矩形面積并的辦法, 不過這次我們不乘高, 不算面積罷了.

    需要注意的是, 由于周長的線會被重複覆寫, 我們每次需要和上一次的作差.

    但是這樣僅僅是 x 軸的, 不過我可以再y軸做一次加起來就可以了

  • 示範 x 軸求長度和的部分
    矩形面積并、矩形面積交、矩形周長并（線段樹、掃描線總結）HDU 1542 [POJ 1151] Atlantis （矩形面積并）HDU 1255 覆寫的面積 （矩形面積交）HDU 1828 [POJ 1177] Picture（矩形周長并）
  • 代碼一: 
//
//  Created by TaoSama on 2015-07-15
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

int n, m[];
int sum[N << ], cnt[N << ], all[][N];
struct Seg {
    int l, r, h, d;
    Seg() {}
    Seg(int l, int r, int h, int d): l(l), r(r), h(h), d(d) {}
    bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[][N];

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

void push_up(int p, int l, int r, int rt) {
    if(cnt[rt]) sum[rt] = all[p][r + ] - all[p][l];
    else if(l == r) sum[rt] = ;
    else sum[rt] = sum[rt << ] + sum[rt <<  | ];
}

void update(int p, int L, int R, int v, int l, int r, int rt) {
    if(L <= l && r <= R) {
        cnt[rt] += v;
        push_up(p, l, r, rt);
        return;
    }

    int m = l + r >> ;
    if(L <= m) update(p, L, R, v, lson);
    if(R > m) update(p, L, R, v, rson);
    push_up(p, l, r, rt);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    while(scanf("%d", &n) == ) {
        for(int i = ; i <= n; ++i) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            all[][i] = x1, all[][i + n] = x2;
            all[][i] = y1, all[][i + n] = y2;
            a[][i] = Seg(x1, x2, y1, );
            a[][i + n] = Seg(x1, x2, y2, -);
            a[][i] = Seg(y1, y2, x1, );
            a[][i + n] = Seg(y1, y2, x2, -);
        }
        n <<= ;
        sort(all[] + , all[] +  + n);
        m[] = unique(all[] + , all[] +  + n) - all[] - ;
        sort(all[] + , all[] +  + n);
        m[] = unique(all[] + , all[] +  + n) - all[] - ;
        sort(a[] + , a[] +  + n);
        sort(a[] + , a[] +  + n);

//      for(int i = 0; i < 2; ++i){
//          for(int j = 1; j <= m[i]; ++j) cout << all[i][j] <<' '; cout << endl;
//      } cout << endl;

        int ans = ;
        for(int i = ; i < ; ++i) {
            int t = , last = ;
            memset(cnt, , sizeof cnt);
            memset(sum, , sizeof sum);
            for(int j = ; j <= n; ++j) {
                int l = lower_bound(all[i] + , all[i] +  + m[i], a[i][j].l) - all[i];
                int r = lower_bound(all[i] + , all[i] +  + m[i], a[i][j].r) - all[i];
                if(l < r) update(i, l, r - , a[i][j].d, , m[i], );
                t += abs(sum[] - last);
                last = sum[];
            }
            ans += t;
        }
        printf("%d\n", ans);
    }
    return ;
}
  • 分析二:

    當然我們也可隻對x軸做一次掃描線, 隻要同時維護 y 軸豎線(就是求矩形面積并的時候的高)的個數, vtl記錄豎線的個數

    需要的注意的是豎線重合的情況, 需要再開變量 lbd,rbd 來判斷重合, 避免重複計算

  • 代碼二: 
//
//  Created by TaoSama on 2015-07-15
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N =  + , INF = , MOD =  + ;

int n;
int sum[N << ], cnt[N << ], vtl[N << ];
bool lbd[N << ], rbd[N << ];
struct Seg {
    int l, r, h, d;
    Seg() {}
    Seg(int l, int r, int h, int d): l(l), r(r), h(h), d(d) {}
    bool operator< (const Seg& rhs) const {return h < rhs.h;}
} a[N];

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

void push_up(int l, int r, int rt) {
    if(cnt[rt]) {
        lbd[rt] = rbd[rt] = true;
        sum[rt] = r +  - l;
        vtl[rt] = ;
    }
//葉子節點的下面的節點也是0 不這樣也可以(那就要數組開大 小心RE)
    else if(l == r) sum[rt] = vtl[rt] = lbd[rt] = rbd[rt] = ;
    else {
        lbd[rt] = lbd[rt << ];
        rbd[rt] = rbd[rt <<  | ];
        sum[rt] = sum[rt << ] + sum[rt <<  | ];
        vtl[rt] = vtl[rt << ] + vtl[rt <<  | ];
        if(rbd[rt << ] && lbd[rt <<  | ]) vtl[rt] -= ; //兩條線重合
    }
}

void update(int L, int R, int v, int l, int r, int rt) {
    if(L <= l && r <= R) {
        cnt[rt] += v;
        push_up(l, r, rt);
        return;
    }
    int m = l + r >> ;
    if(L <= m) update(L, R, v, lson);
    if(R > m) update(L, R, v, rson);
    push_up(l, r, rt);
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio();

    while(scanf("%d", &n) == ) {
        int Min = , Max = -;
        for(int i = ; i <= n; ++i) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            Min = min(Min, x1);
            Max = max(Max, x2);
            a[i] = Seg(x1, x2, y1, );
            a[i + n] = Seg(x1, x2, y2, -);
        }
        n <<= ;
        sort(a + , a +  + n);

//      memset(sum, 0, sizeof sum); 所有覆寫最後都被清除了 不需要初始化了
//      memset(cnt, 0, sizeof cnt);
//      memset(lbd, false, sizeof lbd);
//      memset(rbd, false, sizeof rbd);

        int ans = , last = ;
        for(int i = ; i <= n; ++i) {
            if(a[i].l < a[i].r) update(a[i].l, a[i].r - , a[i].d, Min, Max - , );
            ans += vtl[] * (a[i + ].h - a[i].h);
            ans += abs(sum[] - last);
            last = sum[];
        }
        printf("%d\n", ans);
    }
    return ;
}
算法導學 資料結構 - 線段樹 ········↓↓Editorials↓↓······· 線段樹 掃描線 矩形面積并 矩形面積交 矩形周長并
上一篇: 設計模式—JDK動态代理
下一篇: Atlantis 線段樹經典問題 矩形面積并

繼續閱讀