hdu 1255 覆盖的面积

覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2218 Accepted Submission(s): 1093

Problem Description

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

Input

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

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

Output

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

Sample Input

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

Sample Output

7.63
0.00

Author

Ignatius.L & weigang Lee

Recommend

Ignatius.L

//线段树求面积的并，+个值代表区间内被覆盖2次的长度

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 2003
#define lson l,m,k<<1
#define rson m,r,k<<1|1
using namespace std;
struct segment
{
    double one,two;
    int cover;
};
struct line
{
    double x,y1,y2;
    int flag;
    bool operator<(const line&L)const
    {
        return x<L.x;
    }
};
segment st[N<<2];
line li[N];
double rcy[N];
void build(int l,int r,int k)
{
    st[k].cover=st[k].one=st[k].two=0;
    if(l+1==r)
     return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void up(int &k,int &l,int &r)
{
    if(st[k].cover)
    {
        st[k].one=rcy[r]-rcy[l];
        if(st[k].cover>1)
          st[k].two=rcy[r]-rcy[l];
        else
        {
           if(l+1==r){st[k].two=0;return;}
           st[k].two=st[k<<1].one+st[k<<1|1].one;
        }
    }
    else
    {
        if(l+1==r){st[k].one=st[k].two=0;return;}
        st[k].one=st[k<<1].one+st[k<<1|1].one;
        st[k].two=st[k<<1].two+st[k<<1|1].two;
    }
}
int flag;
void update(double &y1,double &y2,int l,int r,int k)
{
    if(y1<=rcy[l]&&rcy[r]<=y2)
    {
        st[k].cover+=flag;
        up(k,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(y1<rcy[m]) update(y1,y2,lson);
    if(y2>rcy[m]) update(y1,y2,rson);
    up(k,l,r);
}
int main()
{
    double S;
    int n,T;
    int i,j,k;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(j=i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            li[j].x=x1;li[j].y1=y1;li[j].y2=y2;
            li[j].flag=1;
            rcy[j++]=y1;rcy[j]=y2;
            li[j].x=x2;li[j].y1=y1;li[j].y2=y2;
            li[j++].flag=-1;
        }
        sort(li,li+j);
        sort(rcy,rcy+j);
        for(k=0,i=1;i<j;i++)
         if(rcy[i]!=rcy[k])
           rcy[++k]=rcy[i];//郁闷的是这里i写成了k，检查了N久、、、、
        build(0,k,1);
        S=0;j--;
        for(i=0;i<j;i++)
        {
            flag=li[i].flag;
            update(li[i].y1,li[i].y2,0,k,1);
            S+=st[1].two*(li[i+1].x-li[i].x);
        }
        printf("%.2lf\n",S);
    }
    return 0;
}
//在写到线段树计算体积并3次以上的题目时、发现up了函数的问题

//感觉函数内部的值没有明确含义，现在想想都觉得有可能有问题

//所以改了下代码，正确确定下含义

//one 代表被覆盖一次的长度，two代表2次以上的（以前感觉自己脑袋里面这两个的定义都不明确）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 2003
#define lson l,m,k<<1
#define rson m,r,k<<1|1
using namespace std;
struct segment
{
    double one,two;
    int cover;
};
struct line
{
    double x,y1,y2;
    int flag;
    bool operator<(const line&L)const
    {
        return x<L.x;
    }
};
segment st[N<<2];
line li[N];
double rcy[N];
void build(int l,int r,int k)
{
    st[k].cover=st[k].one=st[k].two=0;
    if(l+1==r)
     return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void up(int &k,int &l,int &r)
{
    if(st[k].cover)
    {
        
        if(st[k].cover>1)
          {st[k].one=0; st[k].two=rcy[r]-rcy[l];}
        else
        {  
           if(l+1==r){st[k].one=rcy[r]-rcy[l];st[k].two=0;return;}
           st[k].two=st[k<<1].one+st[k<<1|1].one+st[k<<1].two+st[k<<1|1].two;
           st[k].one=rcy[r]-rcy[l]-st[k].two;
        }
    }
    else
    {
        if(l+1==r){st[k].one=st[k].two=0;return;}
        st[k].one=st[k<<1].one+st[k<<1|1].one;
        st[k].two=st[k<<1].two+st[k<<1|1].two;
    }
}
int flag;
void update(double &y1,double &y2,int l,int r,int k)
{
    if(y1<=rcy[l]&&rcy[r]<=y2)
    {
        st[k].cover+=flag;
        up(k,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(y1<rcy[m]) update(y1,y2,lson);
    if(y2>rcy[m]) update(y1,y2,rson);
    up(k,l,r);
}
int main()
{
    double S;
    int n,T;
    int i,j,k;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(j=i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            li[j].x=x1;li[j].y1=y1;li[j].y2=y2;
            li[j].flag=1;
            rcy[j++]=y1;rcy[j]=y2;
            li[j].x=x2;li[j].y1=y1;li[j].y2=y2;
            li[j++].flag=-1;
        }
        sort(li,li+j);
        sort(rcy,rcy+j);
        for(k=0,i=1;i<j;i++)
         if(rcy[i]!=rcy[k])
           rcy[++k]=rcy[i];
        build(0,k,1);
        S=0;j--;
        for(i=0;i<j;i++)
        {
            flag=li[i].flag;
            update(li[i].y1,li[i].y2,0,k,1);
            S+=st[1].two*(li[i+1].x-li[i].x);
        }
        printf("%.2lf\n",S);
    }
    return 0;
}