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

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 ;
}