覆盖的面积

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

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000. 

注意:本题的输入数据较多,推荐使用scanf读入数据. 

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数. 

Sample Input

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

Sample Output

7.63
0.00

C++版本一

#include <iostream>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>

using namespace std;

const int N=10000+10;
int t,n,cnt=0;
double x,x2,y,y2;
double tree[N],tree2[N];
int flag[N];
double X[N];
void init(){
    memset(tree,0.0,sizeof(tree));
    memset(tree2,0.0,sizeof(tree2));
    memset(flag,0,sizeof(flag));
    cnt=0;
}
struct node{
    double l,r,y;
    int s;
    node(){};
    node(double l0,double r0,double y0,int s0){
        l=l0;
        r=r0;
        y=y0;
        s=s0;
    }
    bool operator <(const node &S) const{
        return y<S.y;
    }
}G[N];
void pushup(int i,int l,int r){

    if(flag[i])
        tree[i]=X[r+1]-X[l];
    else if(l==r)
        tree[i]=0;
    else
        tree[i]=tree[i<<1]+tree[i<<1|1];
    if(flag[i]>1)
        tree2[i]=X[r+1]-X[l];
    else if(l==r)
        tree2[i]=0;
    else if(flag[i]==1)
        tree2[i]=tree[i<<1]+tree[i<<1|1];
    else
        tree2[i]=tree2[i<<1]+tree2[i<<1|1];

}
void updata(int i,int l,int r,int L,int R,int C){
    if(L<=l&&r<=R){
        flag[i]+=C;
        pushup(i,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(R<=m)
        updata(i<<1,l,m,L,R,C);
    else if(m<L)
        updata(i<<1|1,m+1,r,L,R,C);
    else{
        updata(i<<1,l,m,L,m,C);
        updata(i<<1|1,m+1,r,m+1,R,C);
    }
    pushup(i,l,r);
}
int main()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&x,&y,&x2,&y2);
            G[++cnt]=node(x,x2,y,1);
            X[cnt]=x;
            G[++cnt]=node(x,x2,y2,-1);
            X[cnt]=x2;
        }
        sort(X+1,X+cnt+1);
        sort(G+1,G+cnt+1);
        int k=1;

        for(int i=2;i<=cnt;i++){
            if(X[i]!=X[i+1])    X[++k]=X[i];
        }
        double ans=0;
        for(int i=1;i<cnt;i++){
            int l=lower_bound(X+1,X+k+1,G[i].l)-X;
            int r=lower_bound(X+1,X+k+1,G[i].r)-X-1;
            //cout << tree[1] << endl;
            updata(1,1,k,l,r,G[i].s);
            ans+=tree2[1]*(G[i+1].y-G[i].y);

        }

        printf("%.2f\n",ans+0.0001);

    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

首先感谢一下 Titanium：http://acm.hdu.edu.cn/showproblem.php?pid=1255 从他的博客中得到了思路

怎么计算出重复的面积。

遇到这个求相交矩形的面积的时候，我第一反应就是将cnt标记下推，然后每次都将标记下推， 最后根据cnt的值来模仿1中求面积的方式来求，然后实现起来很复杂，并且估计会超时，所以就百度寻求了一波帮助。

我们先规定sum2 为 至少出现1次时统计的长度 sum为至少出现2次时的长度

如果某个区间的cnt >= 2 那么 就表示这个这个区间的所有长度都是有效长度， sum就等于这个区间的总长度

当cnt == 1时， 表示这整个区间线段至少出现过一次  并且这个区间内的部分线段可能会出现好多次 

这个时候访问这个节点的左子树和右子树的sum2，sum = sum2(左子树）+sum2（右子树）。

因为这个区间的cnt == 1 表示目前这个区间的长度都至少出现过了一次， 由于是区间更新且没有下推cnt标记

如果左子树或右子树上sum2 != 0， 那么表示在左子树或右子树上又出现了一次。

那么子树上的一次+目前区间的一次 就能保证出现两次（及以上）。

（请读者充分理解线段树的区域更新， 如果cnt 上有值的话，那么表示 这个区间被完全覆盖的。 

如果区间A被完全覆盖了， 那么会在区间A对应的cnt++， 然后 进行更新和返回（return；）

但是由于不下推， 所以A的左子树或者右子树上的cnt都不会发生变化。所以，如果A的左子树或右子树上

的cnt不为0,那么一定有另一条线扫描到了左子树或者右子数，并且没有完全覆盖区间A。

所以，如果A的cnt == 1并且 A的子树上有值，那么子树上的线段长度和就是至少访问过2次的线段长度和了）；

当然 如果 l==r的时候有效长度还是为0的， 因为叶子节点没有长度。

https://www.cnblogs.com/MingSD/p/8393274.html

#include<iostream>
#include<algorithm>
#include<iomanip>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N = 1e4;
struct Node
{
    double l, r, h;
    int d;
    bool operator < (const Node & x) const
    {
        return h < x.h;
    }
}A[N];
double X[N], sum[N], sum2[N];
int cnt[N];
void Build(int l, int r, int rt)
{
    sum2[rt] = 0.0,cnt[rt] = 0, sum[rt] = 0.0;
    if(l == r) return ;
    int m = l+r >> 1;
    Build(lson);
    Build(rson);
}
void PushUp(int l, int r, int rt)
{
    if(cnt[rt])
    {
        sum2[rt] = X[r] - X[l-1];
    }
    else if(l == r) sum2[rt] = 0.0;
    else sum2[rt] = sum2[rt<<1] + sum2[rt<<1|1];
    if(cnt[rt] > 1)
        sum[rt] = X[r] - X[l-1];
    else if(l == r) sum[rt] = 0;
    else if(cnt[rt] == 1) sum[rt] = sum2[rt<<1]+sum2[rt<<1|1];
    else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void Revise(int L, int R, int C, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        cnt[rt] += C;
        PushUp(l,r,rt);
        return ;
    }
    int m = l+r >> 1;
    if(L <=m) Revise(L,R,C,lson);
    if(m < R) Revise(L,R,C,rson);
    PushUp(l,r,rt);
}
void Add(double l, double r, double h, int d, int i)
{
    A[i].l = l; A[i].h = h;
    A[i].r = r; A[i].d = d;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T, n;
    cin >> T;
    while(T-- && cin >> n)
    {
        int k = 0;
        double x1, y1, x2, y2;
        for(int i = 1; i <= n; i++)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            Add(x1,x2,y1,1,k);
            X[k++] = x1;
            Add(x1,x2,y2,-1,k);
            X[k++] = x2;
        }
        sort(X,X+k);
        sort(A,A+k);
        int pos = 1;
        for(int i = 1; i < k; i++)
        {
            if(X[i] != X[i-1])
                X[pos++] = X[i];
        }
        Build(1,pos,1);
        double ans = 0;
        for(int i = 0; i < k-1; i++)
        {
            int l = lower_bound(X,X+pos,A[i].l) - X;
            int r = lower_bound(X,X+pos,A[i].r) - X;
            Revise(l+1,r,A[i].d,1,pos,1);
            ans += (A[i+1].h - A[i].h) * sum[1];
        }
        cout << fixed << setprecision(2) << ans+0.0001 << endl;//莫名其妙样例一的时候没有四舍五入上去
    }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//所以补了一点上去就给过了
    return 0;
}