HDU 1255 扫描线

扫描线处理矩形覆盖过至少两次的区域的面积.

把callen函数的修改一下即可

data[k].len表示被覆盖的长度

data[k].sum表示被覆盖两次以上的长度

#include "stdio.h"
#include "string.h"
#include "algorithm"
#include "math.h"
using namespace std;

struct Mark
{
    double x,ml,mr;
    int flag;
}mark[50010];

struct Data
{
    double ml,mr,s,len,sum;
    int l,r,lazy;
}data[50010];

double y[50010];

bool cmp(Mark a,Mark b)
{
    return a.x-b.x<0.0000001;
}

void build(int l,int r,int k)
{
    int mid;
    data[k].l=l;
    data[k].r=r;
    data[k].ml=y[l];
    data[k].mr=y[r];
    data[k].s=data[k].lazy=0;
    data[k].len=data[k].sum=0;
    if (l+1==r) return ;

    mid=(l+r)/2;

    build(l,mid,k*2);
    build(mid,r,k*2+1);
}



void callen(int k)
{
    if (data[k].s>1)
    {
        data[k].len=data[k].mr-data[k].ml;
        data[k].sum=data[k].mr-data[k].ml;
    }
    else
        if (data[k].s==1)
    {
        data[k].len=data[k].mr-data[k].ml;
        if (data[k].l+1==data[k].r) data[k].sum=0;
        else
            data[k].sum=data[k*2].len+data[k*2+1].len;
    }
    else
        if (data[k].l+1==data[k].r)
    {
        data[k].len=0;
        data[k].sum=0;
    }
    else
    {
        data[k].len=data[k*2].len+data[k*2+1].len;
        data[k].sum=data[k*2].sum+data[k*2+1].sum;
    }
}

void updata(int k,Mark b)
{
    if (data[k].ml==b.ml && data[k].mr==b.mr)
    {
        data[k].s+=b.flag;
        callen(k);
        return ;
    }


    if (b.mr<=data[k*2].mr) updata(k*2,b);
    else
        if (b.ml>=data[k*2+1].ml) updata(k*2+1,b);
    else
    {
        Mark c;
        c=b;
        c.mr=data[k*2].mr;
        updata(k*2,c);
        c=b;
        c.ml=data[k*2+1].ml;
        updata(k*2+1,c);
    }
    callen(k);
}


int main()
{
    int Case,n,i,len,cnt;
    double sum,x1,y1,x2,y2;
    scanf("%d",&Case);
    while (Case--)
    {
        cnt=0;
        scanf("%d",&n);
        for (i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            mark[cnt].x=x1;
            mark[cnt].ml=y1;
            mark[cnt].mr=y2;
            mark[cnt].flag=1;
            y[cnt++]=y1;
            mark[cnt].x=x2;
            mark[cnt].ml=y1;
            mark[cnt].mr=y2;
            mark[cnt].flag=-1;
            y[cnt++]=y2;
        }

        sort(mark,mark+cnt,cmp);
        sort(y,y+cnt);
        len=1;
        for (i=1;i<cnt;i++)
            if (y[i]!=y[i-1])
        {
            y[len++]=y[i];
        }
        len--;
        build(0,len,1);

        sum=0;
        updata(1,mark[0]);
        for (i=1;i<cnt;i++)
        {

            sum+=data[1].sum*(mark[i].x-mark[i-1].x);
            updata(1,mark[i]);

        }


        printf("%.2lf\n",sum);
    }
    return 0;
}

HDU 1255 扫描线

原文：http://blog.csdn.net/u011932355/article/details/44538661