覆盖的面积_牛客博客

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

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