HDU - 1255 覆盖的面积（线段树求矩形面积交 扫描线+离散化）

链接：线段树求矩形面积并 扫描线+离散化

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

2、看完线段树求矩形面积并 的方法后，再看这题，求的是矩形面积交，类同。

求面积时，用被覆盖2次以上的那一段乘以扫描线的距离即可，具体实现见代码。

3、

/*

HDU 1255 覆盖的面积

求矩形面积交（离散化+线段树）

给定一些矩形

求被这些矩形覆盖过至少两次的区域的面积

这里的方法是：线段树求矩形面积交 扫描线+离散化

左右扫描（x轴扫描），把y轴上的线段离散化

*/

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

const int MAXN=;

struct Node

{

    int l,r;//离散化后的y值

    double lf,rf;//原来的y值，lf代表l原来的y值，rf代表r原来的y值

    int cnt;//当前段被覆盖过几次

    double lenOnce;//当前段中覆盖一次以上的长度

    double lenTwice;//当前段中覆盖两次以上的长度

} segTree[MAXN*];

struct Line

{

    double x;//也就是对应的扫描线x坐标

    double y1,y2;//线段的端点坐标

    double f;//1表示一个矩形左边的边，-1表示右边的边

} line[MAXN];

double y[MAXN];

bool cmp(Line a,Line b)

{

    return a.x<b.x;

}

void Build(int i,int l,int r)

{

    segTree[i].l=l;

    segTree[i].r=r;

    segTree[i].lenOnce=;

    segTree[i].lenTwice=;

    segTree[i].lf=y[l];

    segTree[i].rf=y[r];

    if(l+==r)return;

    int mid=(l+r)>>;

    Build(i<<,l,mid);

    Build((i<<)|,mid,r);

}

void calen(int i)

{

    if(segTree[i].cnt>=)//被线段覆盖次数>=2

    {

        segTree[i].lenOnce=segTree[i].rf-segTree[i].lf;

        segTree[i].lenTwice=segTree[i].rf-segTree[i].lf;

        return;

    }

    else if(segTree[i].cnt==)//被线段覆盖次数==1

    {

        segTree[i].lenOnce=segTree[i].rf-segTree[i].lf;

        if(segTree[i].l+==segTree[i].r)segTree[i].lenTwice=;//当是叶子节点时

        else segTree[i].lenTwice=segTree[i<<].lenOnce+segTree[(i<<)|].lenOnce;

        //因为当前线段被覆盖过1次，所以覆盖2次以上的长度是其左右孩子的覆盖1次以上的长度的和

    }

    else//被线段覆盖次数==0

    {

        if(segTree[i].l+==segTree[i].r)//当是叶子节点时

        {

            segTree[i].lenOnce=segTree[i].lenTwice=;

        }

        else

        {//因为当前节点被覆盖次数为0，所以lenOnce和lenTwice的值由左右孩子决定

            segTree[i].lenOnce=segTree[i<<].lenOnce+segTree[(i<<)|].lenOnce;

            segTree[i].lenTwice=segTree[i<<].lenTwice+segTree[(i<<)|].lenTwice;

        }

    }

}

void update(int i,Line e)

{

    if(e.y1==segTree[i].lf&&segTree[i].rf==e.y2)

    {

        segTree[i].cnt+=e.f;

        calen(i);//更新当前节点信息

        return;

    }

    if(e.y2<=segTree[i<<].rf) update(i<<,e);

    else if(e.y1>=segTree[(i<<)|].lf) update((i<<)|,e);

    else

    {

        Line temp=e;

        temp.y2=segTree[i<<].rf;

        update(i<<,temp);

        temp=e;

        temp.y1=segTree[(i<<)|].lf;

        update((i<<)|,temp);

    }

    calen(i);//更新当前节点信息

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

    int n;

    double x1,y1,x2,y2;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int t=;

        for(int i=; i<=n; i++)

        {

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            //这里题目描述有问题？左下角和右上角

            line[t].y1=y1;

            line[t].y2=y2;

            line[t].x=x1;

            line[t].f=;//左边的边

            y[t]=y1;//y坐标离散化（下端点）

            t++;

            line[t].y1=y1;

            line[t].y2=y2;

            line[t].x=x2;

            line[t].f=-;//右边的边

            y[t]=y2;//y坐标离散化（上端点）

            t++;

        }

        sort(line+,line+t,cmp);//线段按x的值升序排序

        sort(y+,y+t);//y坐标从小下到大排序

        Build(,,t-);//用离散化后的y值（也就是t）建立线段树

        update(,line[]);//从第一条扫描线向右扫描

        double ans=;

        for(int i=; i<t; i++)

        {

            ans+=segTree[].lenTwice*(line[i].x-line[i-].x);

            update(,line[i]);

        }

        printf("%.2lf\n",ans);

    }

    return ;

}

HDU - 1255 覆盖的面积（线段树求矩形面积交 扫描线+离散化）的相关教程结束。