HDU1255覆盖的面积

覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 30 Accepted Submission(s): 23

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

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

Author Ignatius.L & weigang Lee

Recommend Ignatius.L

/*----------------------------------------------
File: F:\ACM源代码\数据结构--线段树\HDU1255.cpp
Date: 2017/5/30 22:21:39
Author: LyuCheng
----------------------------------------------*/
/*
题意：给你很多矩形，然后让你求出最少覆盖两次的面积

思路：扫描线加一点扩展， 计算面积的时候，忽略覆盖一次的长度，x轴上覆盖超过两次的线段长度*高度
    由于我们只需要维护1到max的覆盖长度，所以不需要向下更新，pushup函数，一次维护覆盖过一次的
    长度，一次维护覆盖过两次或者以上的长度
*/

#include<bits/stdc++.h>

#define N 2222
#define lson i*2,l,m
#define rson i*2+1,m+1,r
using namespace std;

struct Node{
    double l,r,h;
    int d;//左右边界，y坐标，是上边界还是下边界
    Node (){}
    Node(double _l,double _r,double _h,int _d){l=_l;r=_r;h=_h;d=_d;}
    bool operator < (const Node &b) const{
        return h<b.h;
    }
};
Node node[N*];//每一个矩形都能产生两条边
double X[N*];//一个矩形有两条边，一条边有两个在x轴上的坐标
double sum[N*];//表示覆盖过的长度
double sumd[N*];//表示覆盖过两次的以上的长度
int setd[N*];

void pushupo(int i,int l,int r){//更新覆盖过一次的
    if(setd[i]){
        sum[i]=X[r+]-X[l];
    }else if(l==r){//如果是叶子结点的话，那么覆盖长度是零
        sum[i]=;
    }else{
        sum[i]=sum[i*]+sum[i*+];
    }
}

void pushupm(int i,int l,int r){//更新覆盖过两次以上的
    if(setd[i]>=){//覆盖过两次或者以上了
        sumd[i]=X[r+]-X[l];
    }else if(l==r){//叶子结点
        sumd[i]=;
    }else if(setd[i]==){
        sumd[i]=sum[i*]+sum[i*+];
    }else{
        sumd[i]=sumd[i*]+sumd[i*+];
    }
}

void update(int ql,int qr,int d,int i,int l,int r){

    if(ql<=l&&r<=qr){
        setd[i]+=d;
        pushupo(i,l,r);
        pushupm(i,l,r);
        return ;
    }

    int m=l+(r-l)/;
    if(ql<=m) update(ql,qr,d,lson);
    if(m<qr) update(ql,qr,d,rson);
    pushupo(i,l,r);
    pushupm(i,l,r);
}

int Seach(double op,int n){//离散化x坐标为整数，这样才能用线段树维护
    int l=,r=n;
    while(r>=l){
        int m=l+(r-l)/;
        if(X[m]==op)
            return m;
        else if(X[m]>op)
            r=m-;
        else
            l=m+;
    }
    return -;
}

void init(){
    memset(sum,,sizeof sum);
    memset(sumd,,sizeof sumd);
    memset(setd,,sizeof setd);
}

int main(){

    // freopen("in.txt","r",stdin);
    int n;
    double x1,x2,y1,y2;
    int len=;
    int cnt=;
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        len=;cnt=;

        for(int i=;i<=n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            node[++cnt]=Node(x1,x2,y1,);
            node[++cnt]=Node(x1,x2,y2,-);
            X[++len]=x1;
            X[++len]=x2;
        }

        sort(node+,node+cnt+);
        sort(X+,X+len+);

        int ans=;

        for(int i=;i<=len;i++)//进行去重操作
            if(X[i]!=X[i-])
                X[++ans]=X[i];

        len=ans;
        double cur=;
        for(int i=;i<cnt;i++){
            int l=Seach(node[i].l,len);
            int r=Seach(node[i].r,len)-;
            if(l<=r)
                update(l,r,node[i].d,,,len);
            cur+=sumd[]*(node[i+].h-node[i].h);
        }
        printf("%.2lf\n",cur);
    }
    return ;
}