覆盖的面积

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

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中求面积的方式来求，然后实现起来很复杂，并且估计会超时，所以就百度寻求了一波帮助。

覆盖的面积

全站热榜