HDU - 1542 Atlantis（區間修改，掃描線，離散化）

​​HDU - 1542 Atlantis​​

題目

在平面上給出 n 個矩形，求矩形并的面積。

分析

首先用掃描線按矩形的水準邊分段，如上圖。在同一段的面積一起計算，即同一種顔色。

具體操作：

從下往上掃描，對于每一段的高，即為兩個相鄰的水準邊之間的垂直距離。

而對于每一段的寬，就是多個矩形的實際覆寫距離，這一部分用線段樹的區間覆寫來維護。

如果掃到的這條邊是某矩形的下邊，則往區間插入這條線段

如果掃到的這條邊是某矩形的上邊，則往區間删除這條線段

就可以得到目前的那一段的實際覆寫距離。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 9999991;
const int N = 2e5 + 10;

int n, cas = 1, cnt;
double tmp[N];        //離散化數組
int col[N];
double tr[N];         //區間實際覆寫距離
struct node{          //矩形的上下兩條線段
    double l, r, h;   //線段左右端點，高
    int s;            //線段是矩形上邊還是下邊
    node(){}
    node(double l, double r, double h, int s):l(l),r(r),h(h),s(s){}
    bool operator < (const node & b) const{
        return h < b.h;
    }
} seg[N];

void pushup(int rt, int l, int r){
    if(col[rt]){            //如果有區間覆寫标記，實際覆寫長度為 tmp數組內插補點
        tr[rt] = tmp[r + 1] - tmp[l];
    }else if(l == r){
        tr[rt] = 0;
    }else{                  //沒的話就是左右區間有效長度相加
        tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
    }
}

void update(int L, int R, int c, int l, int r, int rt){
    if(L <= l && r <= R){
        col[rt] += c;
        pushup(rt, l, r);
        return;
    }
    int m = l + r >> 1;
    if(L <= m){
        update(L, R, c, lson);
    }
    if(R > m){
        update(L, R, c, rson);
    }
    pushup(rt, l, r);
}

int main()
{
    while(~scanf("%d", &n) && n){
        cnt = 0;
        while(n--){
            double a, b, c, d;
            scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
            tmp[cnt] = a;                       // tmp 數組存 x 坐标，線段樹以 x 坐标建樹
            seg[cnt++] = node(a, c, b, 1);      // seg 數組存矩形的每一條水準邊，下邊為1，上邊為-1
            tmp[cnt] = c;
            seg[cnt++] = node(a, c, d, -1);
        }
        sort(tmp, tmp + cnt);
        sort(seg, seg + cnt);                   //按高度排序
        int k = 1;                                      
        for (int i = 1; i < cnt; i++){          //去重，便于後面離散化
            if(tmp[i] != tmp[i-1]){             //預設 tmp[0] 排好了，從 1 開始
                tmp[k++] = tmp[i];
            }
        }
        memset(col, 0, sizeof(col));
        memset(tr, 0, sizeof(tr));
        double ans = 0;
        for (int i = 0; i < cnt - 1; i++){      //每次處理一段的面積， 處理 cnt - 1段
            int l = upper_bound(tmp, tmp + k, seg[i].l) - tmp - 1;
            int r = upper_bound(tmp, tmp + k, seg[i].r) - tmp - 2;
            if (l <= r){
                update(l, r, seg[i].s, 0, k - 1, 1);
            }
            ans += tr[1] * (seg[i + 1].h - seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n", cas++, ans);
    }
    return 0;
}