首页 > 其他 > 详细

hdu1255--覆盖的面积(线段树+离散化+扫描线)

时间:2014-08-12 19:01:42      阅读:322      评论:0      收藏:0      [点我收藏+]

E - 覆盖的面积
Time Limit:5000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status

Description

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

bubuko.com,布布扣

 

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
 

刚刚接触扫描线,一开始只是求了n个矩形的并的体积,这次求的是覆盖两次以上的面积。

首先给出了n个矩形的坐标,对于y坐标离散化,从左向右扫描,在求并的面积时,用标记sum1存储了出现过的线段的长度,使用(p[i].x-p[i-1].x)*cl[1].sum1求解了每一部分的面积,而在求覆盖面积的时候,还要定义一个变量sum2,储存下在控制区内出现两次的总和。

在sum1的push_up中,如果lazy标记不是0,那么该段全部出现,那么cl[rt].sum1 = cl[rt].r - cl[rt].l ;否则该节点的值就是左右两个子树的和。

在sum2的push_up中,如果lazy表标记的结果是2,那么该段全部出现,sum2的值就是该段的长度,如果lazy的标记是1表示该段在该节点全部出现,那么出现过两次的长度就是在该节点的左右子节点中出现的长度,即 cl[rt].sum2  = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;,如果该节点的lazy是0,那么该段的sum2也就等于左右子节点的sum2之和。


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 3000
struct node1{
    double x, y1 , y2 ;
    int flag ;
} p[maxn];
struct node{
    double l , r ;
    double sum1 , sum2 ;
} cl[maxn<<3];
double s[maxn<<1] ;
int lazy[maxn<<3] ;
bool cmp(node1 a,node1 b)
{
    return a.x <b.x ;
}
void push_up(int rt)
{
    if( lazy[rt] )
        cl[rt].sum1 = cl[rt].r - cl[rt].l ;
    else
        cl[rt].sum1 = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;
    if( lazy[rt] > 1 )
        cl[rt].sum2 = cl[rt].r - cl[rt].l ;
    else if(lazy[rt] == 1)
        cl[rt].sum2 = cl[rt<<1].sum1 + cl[rt<<1|1].sum1 ;
    else
        cl[rt].sum2 = cl[rt<<1].sum2 + cl[rt<<1|1].sum2 ;
}
void creat(int rt,int l,int r)
{
    cl[rt].l = s[l] ;
    cl[rt].r = s[r] ;
    if( r - l >1 )
    {
        creat(rt<<1,l,(l+r)/2);
        creat(rt<<1|1,(l+r)/2,r);
        push_up(rt);
    }
    else
    {
        cl[rt].sum1 = cl[rt].sum2 = 0 ;
        cl[rt<<1].sum1 = cl[rt<<1].sum2 = 0 ;
        cl[rt<<1|1].sum1 = cl[rt<<1|1].sum2 = 0 ;
    }
}
void update(int rt,double l,double r,int flag)
{
    if( cl[rt].l== l && cl[rt].r == r )
    {
        lazy[rt] += flag ;
        push_up(rt);
    }
    else
    {
        if( cl[rt<<1].r > l )
        {
            double x = min(r,cl[rt<<1].r);
            update(rt<<1,l,x,flag);
        }
        if( cl[rt<<1|1].l < r )
        {
            double x = max(l,cl[rt<<1|1].l);
            update(rt<<1|1,x,r,flag);
        }
        push_up(rt);
    }
}
int main()
{
    int t , n , m , i , j ;
    double x1, y1 , x2 , y2 , ans ;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i = 0 ; i < n ; i++)
        {
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
            p[i].x = x1 ;
            p[i].y1 = y1 ;
            p[i].y2 = y2 ;
            p[i].flag = 1 ;
            p[i+n].x = x2 ;
            p[i+n].y1 = y1 ;
            p[i+n].y2 = y2 ;
            p[i+n].flag = -1 ;
            s[i+1] = y1 ;
            s[i+n+1] = y2 ;
        }
        memset(lazy,0,sizeof(lazy));
        sort(s+1,s+2*n+1);
        sort(p,p+2*n,cmp);
        m = unique(s+1,s+(2*n+1))-(s+1);
        creat(1,1,m);
        update(1,p[0].y1,p[0].y2,p[0].flag);
        ans = 0 ;
        for(i = 1 ; i < 2*n ; i++)
        {
            ans += (p[i].x - p[i-1].x)*cl[1].sum2 ;
            update(1,p[i].y1,p[i].y2,p[i].flag);
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}



hdu1255--覆盖的面积(线段树+离散化+扫描线),布布扣,bubuko.com

hdu1255--覆盖的面积(线段树+离散化+扫描线)

原文:http://blog.csdn.net/winddreams/article/details/38519127

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!