hdu1255 覆盖的面积（线段树面积交）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1255

面积交与面积并相似相比回了面积并，面积交一定会有思路，当然就是cover标记大于等于两次时。

但是操作起来发现与面积并有些不同。面积交要从面积并的状态转过来。当cover值为1的时候交

的长度可以为（p为当前节点len1为并的区间长度，len2为交的区间长度）

T[p].len2=T[p<<1].len1+T[(p<<1)|1].len1。这样也能满足cover为2.

当cover为2是那就与并的操作相同。

这题是一道比较简单的面积交模版题，可以拿来练练手。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

const int M = 2e3 + 10;

double se[M << 1];

struct ss {

    double l , r , h;

    int flag;

}s[M << 1];

struct TnT {

    int l , r , add;

    double len1 , len2;

}T[M << 2];

bool cmp(ss a , ss b) {

    return a.h < b.h;

}

void build(int l , int r , int p) {

    int mid = (l + r) >> 1;

    T[p].l = l , T[p].r = r , T[p].len1 = T[p].len2 = T[p].add = 0;

    if(l == r)

        return ;

    build(l , mid , p << 1);

    build(mid + 1 , r , (p << 1) | 1);

}

void pushup(int p) {

    if(T[p].add >= 2) {

        T[p].len2 = se[T[p].r + 1] - se[T[p].l];

        T[p].len1 = T[p].len2;

    }

    else if(T[p].add == 1) {

        T[p].len1 = se[T[p].r + 1] - se[T[p].l];

        if(T[p].l == T[p].r) {

            T[p].len2 = 0;

        }

        else {

            T[p].len2 = T[p << 1].len1 + T[(p << 1) | 1].len1;

        }

    }

    else {

        if(T[p].l == T[p].r) {

            T[p].len1 = T[p].len2 = 0;

        }

        else {

            T[p].len1 = T[p << 1].len1 + T[(p << 1) | 1].len1;

            T[p].len2 = T[p << 1].len2 + T[(p << 1) | 1].len2;

        }

    }

}

void updata(int l , int r , int p , int ad) {

    int mid = (T[p].l + T[p].r) >> 1;

    if(T[p].l == l && T[p].r == r) {

        T[p].add += ad;

        pushup(p);

        return ;

    }

    if(mid >= r) {

        updata(l , r , p << 1 , ad);

    }

    else if(mid < l) {

        updata(l , r , (p << 1) | 1 , ad);

    }

    else {

        updata(l , mid , p << 1 , ad);

        updata(mid + 1 , r , (p << 1) | 1 , ad);

    }

    pushup(p);

}

int main() {

    int t , n;

    scanf("%d" , &t);

    while(t--) {

        scanf("%d" , &n);

        int cnt = 0;

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

            double x1 , x2 , y1 , y2;

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

            s[i].flag = 1;

            s[i].l = x1;

            s[i].r = x2;

            s[i].h = y1;

            se[++cnt] = x1;

            se[++cnt] = x2;

            s[i + n].flag = -1;

            s[i + n].l = x1;

            s[i + n].r = x2;

            s[i + n].h = y2;

        }

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

        sort(s + 1 , s + 1 + 2 * n , cmp);

        cnt = unique(se + 1 , se + 1 + cnt) - se - 1;

        build(1 , cnt , 1);

        int l , r;

        l = upper_bound(se + 1 , se + 1 + cnt , s[1].l) - se - 1;

        r = upper_bound(se + 1 , se + 1 + cnt , s[1].r) - se - 1;

        r--;

        double area = 0;

        updata(l , r , 1 , s[1].flag);

        for(int i = 2 ; i <= 2 * n ; i++) {

            area += T[1].len2 * (s[i].h - s[i - 1].h);

            l = upper_bound(se + 1 , se + 1 + cnt , s[i].l) - se - 1;

            r = upper_bound(se + 1 , se + 1 + cnt , s[i].r) - se - 1;

            r--;

            updata(l , r , 1 , s[i].flag);

        }

        printf("%.2lf\n" , area);

    }

    return 0;

}

巴特西

hdu1255 覆盖的面积（线段树面积交）

最新文章

热门文章