HDU - 1255 覆盖的面积 （线段树求面积交）

时间：2020-12-24 00:47:35

https://cn.vjudge.net/problem/HDU-1255

题意

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

分析

求面积并的题：https://www.cnblogs.com/fht-litost/p/9580330.html

这题求面积交，也就是cover>=2才计算，采用第一种方法就只用小小改动。

以下用了第二种方法。这里得维护覆盖一次以上的长度，和覆盖两次以上的长度。重点在cal()函数。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

const int maxm =  + ;

const int mod = ;

int n;

double y[maxn];

struct LINE{

    double x;

    double y1,y2;

    int flag;

    bool operator <(const LINE &a)const{

        return x<a.x;

    }

}line[maxn];

struct ND{

    double l,r;

    int cover;

    bool f;

    double one;//覆盖一次以上的长度

    double more;//覆盖两次以上的长度

}tree[maxn<<];

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

    tree[rt].l=y[l];

    tree[rt].r=y[r];

    tree[rt].cover=;

    tree[rt].one=tree[rt].more=;

    tree[rt].f=false;

    if(l+==r){

        tree[rt].f=true;

        return;

    }

    int mid = (l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid,r);

}

void cal(int rt){

    if(tree[rt].cover>=){

        tree[rt].more=tree[rt].one=tree[rt].r-tree[rt].l;

    }else if(tree[rt].cover==){

        tree[rt].one=tree[rt].r-tree[rt].l;

        if(tree[rt].f) tree[rt].more=;

        else tree[rt].more=tree[rt<<].one+tree[rt<<|].one;

    }else{

        if(tree[rt].f){

            tree[rt].more=tree[rt].one=;

        }else{

            tree[rt].one=tree[rt<<].one+tree[rt<<|].one;

            tree[rt].more=tree[rt<<].more+tree[rt<<|].more;

        }

    }

}

void update(int rt,double l,double r,int flag){

    if(l==tree[rt].l&&r==tree[rt].r){

        tree[rt].cover+=flag;

        cal(rt);

        return;

    }

    if(tree[rt<<].r>=r) update(rt<<,l,r,flag);

    else if(l>=tree[rt<<|].l) update(rt<<|,l,r,flag);

    else{

        update(rt<<,l,tree[rt<<].r,flag);

        update(rt<<|,tree[rt<<|].l,r,flag);

    }

    cal(rt);

}

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int T,cas=;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        int cnt=-;

        double x1,x2,y1,y2;

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

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

            y[++cnt]=y1;

            line[cnt].x=x1;

            line[cnt].y1=y1;

            line[cnt].y2=y2;

            line[cnt].flag=;

            y[++cnt]=y2;

            line[cnt].x=x2;

            line[cnt].y1=y1;

            line[cnt].y2=y2;

            line[cnt].flag=-;

        }

        sort(y,y++cnt);

        sort(line,line++cnt);

        build(,,cnt);

        update(,line[].y1,line[].y2,line[].flag);

        double area=;

        for(int i=;i<=cnt;i++){

            area+=tree[].more*(line[i].x-line[i-].x);

            update(,line[i].y1,line[i].y2,line[i].flag);

        }

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

    }

    return ;

}

相关文章