覆盖的面积(HDU 1255 线段树)

覆盖的面积

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

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

线段树计算被覆盖部分的面积

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define LL long long

using namespace std;

const int Max = 1000;

typedef struct Tree
{
    int num;
    double OneL,TwoL;//记录区间被覆盖多于一次和两次的长度
}Tree;

Tree Tr[Max*10];

typedef struct Point
{
    double x;
    double y1;
    double y2;
    int op;
    bool operator < (const struct Point a)const
    {
        return x<a.x;
    }

}Point;

Point P[Max*3];

vector <double>y;

int T,n;

void Pushup(int L,int R,int st)
{
    if(Tr[st].num>=2)
    {
        Tr[st].TwoL=Tr[st].OneL=y[R-1]-y[L-1];
        return ;
    }
    if(Tr[st].num==1)
    {
        if(L+1==R)
        {
            Tr[st].TwoL=0;
            Tr[st].OneL=y[R-1]-y[L-1];
        }
        else
        {
            Tr[st].OneL=y[R-1]-y[L-1];
            Tr[st].TwoL=Tr[st<<1].OneL+Tr[st<<1|1].OneL;
        }
        return ;
    }
    if(Tr[st].num==0)
    {
        if(L+1==R)
        {
            Tr[st].OneL=Tr[st].TwoL=0;
        }
        else
        {
            Tr[st].OneL=Tr[st<<1].OneL+Tr[st<<1|1].OneL;
            Tr[st].TwoL=Tr[st<<1].TwoL+Tr[st<<1|1].TwoL;
        }
        return ;
    }
}
void Build(int L,int R,int st)
{
    Tr[st].num=0;
    Tr[st].OneL=Tr[st].TwoL=0;
    if(L+1==R)
    {
        return ;
    }
    int mid = (L+R)>>1;

    Build(L,mid,st<<1);

    Build(mid,R,st<<1|1);

    Pushup(L,R,st);
}

void Update(int L,int R,int st,int l,int r,int d)
{
    if(l>=R||r<=L)
    {
        return ;
    }
    if(L>=l&&R<=r)
    {
        Tr[st].num+=d;
        Pushup(L,R,st);
        return ;
    }
    int mid = (L+R)>>1;
    if(l<=mid)
    {
        Update(L,mid,st<<1,l,r,d);
    }
    if(r>mid)
    {
        Update(mid,R,st<<1|1,l,r,d);
    }
    Pushup(L,R,st);

}

int main()
{
    double x1,x2,y1,y2;

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d",&n);

        y.clear();

        map<double ,int >M;

        int m=0;

        for(int i=0;i<n;i++)
        {
            scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

            P[m].x=x1; P[m].y1=y1; P[m].op=1; P[m++].y2=y2;

            P[m].x=x2; P[m].y1=y1; P[m].op=-1; P[m++].y2=y2;

            y.push_back(y1);

            y.push_back(y2);
        }

        sort(P,P+m);

        sort(y.begin(),y.end());

        y.erase(unique(y.begin(),y.end()),y.end());//去重

        int sum = y.size();

        for(int i=0;i<sum;i++)//重新编号
        {
            M[y[i]]=i+1;
        }

        double Area =0 ;

        double h;

        Build(1,sum,1);

        for(int i=0;i<m-1;i++)
        {
            Update(1,sum,1,M[P[i].y1],M[P[i].y2],P[i].op);
            h=P[i+1].x-P[i].x;
            Area += (h*Tr[1].TwoL);//计算面积
        }
        printf("%.2f
",Area);
    }
    return 0;
}