线段树扫描线模板

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}template 
     
      inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template 
      
       inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 200;int n, k, cnt[N<<3], cs;double b[N<<2], sum[N<<3];struct Seg{    double l, r, h;    int tag;    Seg(){}    Seg(double l, double r, double h, int tag): l(l), r(r), h(h), tag(tag){}    bool operator < (const Seg &rhs) const {        return h < rhs.h;    }};vector
       
         v;void push_up(int rt, int l, int r){    if(cnt[rt]) sum[rt] = b[r + 1] - b[l];    else if(l == r) sum[rt] = 0;    else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void buildTree(int rt, int l, int r){    if(l == r){        cnt[rt] = sum[rt] = 0;        return;    }    int mid = (l + r) >> 1;    buildTree(rt << 1, l, mid);    buildTree(rt << 1 | 1, mid + 1, r);}void insert(int rt, int l, int r, int il, int ir, int val){    if(l == il && r == ir){        cnt[rt] += val;        push_up(rt, l, r);        return;    }    int mid = (l + r) >> 1;    if(ir <= mid) insert(rt << 1, l, mid, il, ir, val);    else if(il > mid) insert(rt << 1 | 1, mid + 1, r, il, ir, val);    else insert(rt << 1, l, mid, il, mid, val), insert(rt << 1 | 1, mid + 1, r, mid + 1, ir, val);    push_up(rt, l, r);}void init(){    k = 0;    v.clear(), full(b, 0);    full(sum, 0), full(cnt, 0);}int main(){    double x1, y1, x2, y2;    while(~scanf("%d", &n) && n){        init();        for(int i = 1; i <= n; i ++){            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);            v.emplace_back(x1, x2, y1, 1);            v.emplace_back(x1, x2, y2, -1);            b[++k] = x1, b[++k] = x2;        }        sort(b + 1, b + k + 1);        k = (int)(unique(b + 1, b + k + 1) - b - 1);        sort(v.begin(), v.end());        buildTree(1, 1, k - 1);        double ans = 0;        for(int i = 0; i < v.size() - 1; i ++){            int l = (int)(lower_bound(b + 1, b + k + 1, v[i].l) - b);            int r = (int)(lower_bound(b + 1, b + k + 1, v[i].r) - b);            r --;            insert(1, 1, k - 1, l, r, v[i].tag);            ans += sum[1] * (v[i + 1].h - v[i].h);        }        printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++ cs, ans);    }    return 0;}