hdu1255 線段樹+掃描線+離散化

hdu1255 線段樹+掃描線+離散化

題意是求矩形覆蓋2次以上的面積

第一道掃面線題 看了網上一些掃描線的講解 沒怎麼看懂 自己試著敲了一下 感覺還行 比較容易懂

關於掃描線的概念就不多說了 直接上題

離散化：對x軸

線段樹 ：對離散後的x值

掃描線：對與x軸平行的邊

注意節點的的子樹 應為必須是一個區間 所有最小區間為為1-2 2-3 3-4 4-5 ··········

#include
#include
#include
#include
using namespace std;
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)

struct node
{
    double y;
    int x1,x2;
    int flash;
}A[3100];
struct Node
{
    double x;
    int tt;
    int ii;
}scatter[3100];
int leap[10000];//標記節點  如果==-1說明當前節點表示的區間不是不是一樣的值   否則為對應的值
int n;
double map[3100];//每個下標對應浮點型x的值
int cmp(Node a,Node b)
{
    return a.x<b.x;
}
int cmp2(Node a,Node b)
{
    if(a.ii!=b.ii) return a.ii<b.ii;
    else return a.x<b.x;
}
int cmp3(node a,node b)
{
    return a.y<b.y;
}
int update(int L,int R,int left,int right,int mark,int k)
{
    int mid=(L+R)/2;
    if(L==left&&right==R)
    {
        if(leap[mark]>=0)
        {
            leap[mark]+=k;    
        }
        else
        {
            update(L,mid,L,mid,LL(mark),k);
            update(mid,R,mid,R,RR(mark),k);
            if(leap[LL(mark)]==leap[RR(mark)]) leap[mark]=leap[LL(mark)];
        }
    }
    else
    {
        if(leap[mark]>=0)
        {
            leap[LL(mark)]=leap[mark];
            leap[RR(mark)]=leap[mark];
        }
        if(right<=mid)
        {
            update(L,mid,left,right,LL(mark),k);
        }
        else if(left>=mid)
        {
            update(mid,R,left,right,RR(mark),k);
        }
        else
        {
            update(L,mid,left,mid,LL(mark),k);
            update(mid,R,mid,right,RR(mark),k);
        }
        if(leap[LL(mark)]==leap[RR(mark)]) leap[mark]=leap[LL(mark)];
        else leap[mark]=-1;
    }
    return 0;
}
double find(int L,int R,int mark)
{
    double dis=0;
    if(leap[mark]>=2)
    {
        dis+=map[R]-map[L];
        return dis;
    }
    if(leap[mark]>=0) return 0;
    int mid=(L+R)/2;
    dis+=find(L,mid,LL(mark))+find(mid,R,RR(mark));
    return dis;
}
int main()
{
    int T,i,j,a,b;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(A,0,sizeof(A));
        memset(map,0,sizeof(map));
        for(i=1;i<=2*n;i+=2)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            A[i].y=y1;
            A[i].flash=1;
            A[i+1].y=y2;
            A[i+1].flash=-1;
            scatter[i].x=x1;
            scatter[i].ii=i;
            scatter[i+1].x=x2;
            scatter[i+1].ii=i;
        }
        sort(scatter+1,scatter+2*n+1,cmp);//對x來離散   應為x值為浮點型  不能成為數組下標
        double k=-1;
        int j=0;
        for(i=1;i<=2*n;i++)
        {
            if(scatter[i].x!=k)
            {
                k=scatter[i].x;
                scatter[i].tt=++j;
                map[j]=scatter[i].x;
            }
            else scatter[i].tt=j;
        }
        sort(scatter+1,scatter+2*n+1,cmp2);
        for(i=1;i<=2*n;i+=2)
        {
            A[i].x1=scatter[i].tt;
            A[i].x2=scatter[i+1].tt;
            A[i+1].x1=scatter[i].tt;
            A[i+1].x2=scatter[i+1].tt;
        }
        sort(A+1,A+2*n+1,cmp3);//把所有與x軸平行的邊按對應的y值排序
        memset(leap,0,sizeof(leap));
        double area=0;
        a=A[1].x1;
        b=A[1].x2;
        update(1,j,a,b,1,1);
        for(i=2;i<=2*n;i++)
        {
              a=A[i].x1;
              b=A[i].x2;
              area+=(A[i].y-A[i-1].y)*find(1,j,1);
              if(A[i].flash==1) update(1,j,A[i].x1,A[i].x2,1,1);
              else update(1,j,A[i].x1,A[i].x2,1,-1);
        }
        printf("%.2lf\n",area);
    }
    return 0;
}