[线段树][扫描线][面积交] HDU 1255

这次写了这个题目之后我发现之前对面积并的那个cal计数的意义还是理解还是有一点偏差:这个东西表示的是当前节点对应的线段整体覆盖的情况。为0时没有被全覆盖(注意不等于没有被覆盖),为1时被全覆盖了1次(意为min(l,r)==1,不代表不大于1),为k时表示min(l,r)==k。而且对应的只是一个节点对应的整个线段,跟只表示当前整段线段的状况,儿子是什么样不知道。。。

这个题也貌似有很多种方法,我参考了一位前辈的博客之后用了Len1表示全覆盖次数≥1的长度,Len2表示全覆盖次数≥2的长度,当然全部都是针对当前节点。Len1的维护方法和面积并的方法完全一样。然后Len2维护的时候就是,如果cnt[o]大于等于2,那么说明当前节点被全覆盖了两次,直接Len2=Len1,如果为1,说明当前节点被全覆盖了一次,那么只需要加上子节点中被全覆盖了一次的Len1就可以了(这样相当于在双亲节点里覆盖了两次),如果是叶子节点,没有孩子,那就直接是0,如果cnt为0,那就只有孩子里面的被全覆盖了两次之和才能更新当前点了。
这里还有一个需要注意的是,如果cnt为0,那么要么说明,当前节点从来没有被计算过,要么说明只计算过子节点,所以不会出现错误。

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<unordered_set>
#include<unordered_map>
#define eps 1e-6
//#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn=1e3+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

struct seg
{
    double lt,rt,y;
    int flag;
    seg(){};
    bool operator<(const struct seg &rhs)const {return y<rhs.y;}
}segs[maxn<<1];
int n,cntx,cnty;
double xs[maxn<<1],ys[maxn<<1];

int getX(double x){return lower_bound(xs+1,xs+1+cntx,x)-xs;}
int getY(double y){return lower_bound(ys+1,ys+1+cnty,y)-ys;}

double Len1[maxn<<4],Len2[maxn<<4];
int cnt[maxn<<4];

void maintain(int o,int l,int r)//[l,r)
{
    if(cnt[o])
        Len1[o]=xs[r]-xs[l];
    else
        Len1[o]=Len1[o<<1]+Len1[o<<1|1];

    if(cnt[o]>1)
        Len2[o]=Len1[o];
    else if(cnt[o]==1&&l<r-1)
        Len2[o]=Len1[o<<1]+Len1[o<<1|1];//the most important
    else if(cnt[o]==1&&l==r-1)
        Len2[o]=0.0;
    else
        Len2[o]=Len2[o<<1]+Len2[o<<1|1];
}


int pl,pr,v;
void update(int o,int l,int r)
{
    if(l==r)return ;
    if(pl<=l&&r<pr)
    {
        cnt[o]+=v;
    }
    else if(l!=r-1)
    {
        int mid=(l+r)>>1;
        if(pl<mid)update(o<<1,l,mid);
        if(mid<pr)update(o<<1|1,mid,r);
    }
    /*有没有return都一样
    else
    {
        return ;
    }
    */
    maintain(o,l,r);
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int T;
    double x1,x2,y1,y2;
    scanf("%d",&T);
    while(T--)
    {
        memset(Len1,0,sizeof(Len1));
        memset(Len2,0,sizeof(Len2));
        memset(cnt,0,sizeof(cnt));
        cntx=cnty=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            xs[++cntx]=x1,xs[++cntx]=x2;
            ys[++cnty]=y1,ys[++cnty]=y2;
            segs[2*i-1].lt=x1,segs[2*i-1].rt=x2,segs[2*i-1].y=y1,segs[2*i-1].flag=1;
            segs[i<<1].lt=x1,segs[i<<1].rt=x2,segs[i<<1].y=y2,segs[i<<1].flag=-1;
        }
        sort(segs+1,segs+1+2*n);
        sort(xs+1,xs+1+2*n);
        sort(ys+1,ys+1+2*n);
        cntx=cnty=1;
        for (int i=2;i<=2*n;i++)
        {
            if(xs[i]!=xs[cntx])
                xs[++cntx]=xs[i];
            if(ys[i]!=ys[cnty])
                ys[++cnty]=ys[i];
        }
        xs[cntx+1]=xs[cntx];
        ys[cnty]=ys[cnty];
        double ans=0.0;
        for (int i=1;i<2*n;i++)
        {
            double ch=segs[i+1].y-segs[i].y;
            pl=getX(segs[i].lt),pr=getX(segs[i].rt)+1,v=segs[i].flag;
            update(1,1,cntx+1);
            ans+=Len2[1]*(ch);
        }
        printf("%.2f\n",ans);
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据