注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2731(hnoi 2012) 三角面积覆盖  

2013-02-09 17:02:28|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这道题我是膜拜的vfleaking大神题解

看到那个暴力算法我还不确定我的理解,特地去问了一下

结果真够暴力的……

其实有正解的

但是这个爆搞加优化跑的飞样的

就好像bzoj 1020一样,莫涛集训队作业里的题解其实也是爆搞加剪枝,但跑的真的很快,在bzoj上rank前几的都是用的这个方法

这道题应该也是吧……

方法是这样的

从最低点弄根扫描线,一直到最高点,每次扫描线++

是的,你没看错,就是++!不要总想着怎么离散化,++足矣,离散化的话情况就太太太复杂了

两根扫描之间的面积,就是下面那根扫描线被覆盖的长度+上面那根扫描线被非底边覆盖的长度,然后除以2。

因为这是若干个高为1的梯形,随便分配率一下就知道了

我们开一个巨大无比的数组!

数组大小1000000!

存的是坐标!sum[i]表示i~i+1被覆盖多少次!

如果sum值0->1或者1->0就更新len值,这一点做过picture的应该都能理解

扫描线上移时,对于覆盖扫描线的三角形我们只要把最右边的那个sum值--就可以了

如果某个三角形跑到了扫描线下方,删了它!

因为有删除操作,于是双向链表闪亮登场了

80分到手了

还有20分怎么弄呢?

插一个三角形的时候,如果这个三角形被覆盖,就不插它

如果覆盖某三角形,删了那个

由于是等腰三角形,我们维护这个三角形在当前扫描线覆盖的左右端点即可,因为如果左右端点被覆盖就肯定被覆盖了

时间复杂度未知

实际效率100+ms

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 10010
#define MAXL 1000010
using namespace std;
double ans,len;
int n,low=MAXL,high,next[MAXN],last[MAXN],sum[MAXL],head=1;
bool mark[MAXN];
struct Triangle
{
    int x,y,d,l,r;
    friend bool operator < (const Triangle &a,const Triangle &b){  return a.y<b.y;  }
    friend bool operator > (const Triangle &a,const Triangle &b){  return a.l<=b.l&&a.r>=b.r;  }
}triangle[MAXN];
void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&triangle[i].x,&triangle[i].y,&triangle[i].d);
        mark[i]=true;
        last[i]=i-1,next[i]=i+1,low=min(low,triangle[i].y),high=max(high,triangle[i].y+triangle[i].d);
        triangle[i].l=triangle[i].x,triangle[i].r=triangle[i].l+triangle[i].d;
    }
    sort(triangle+1,triangle+n+1);
}
void Delete(int p)
{
    if(p==head)  head=next[p];
    next[last[p]]=next[p],last[next[p]]=last[p];
    mark[p]=false;
}
void work()
{
    int q[MAXN];
    for(int i=1;i<=n&&triangle[i].y==low;i++)
        for(int j=triangle[i].x;j<triangle[i].r;j++)
        {
            if(sum[j]==0)  len++;
            sum[j]++;
        }
    for(int i=low+1;i<=high;i++)
    {
        double lastlen=len;
        int top=0;
        for(int j=head;triangle[j].y<i&&j<=n;j=next[j])
        {
            Triangle &now=triangle[j];
            now.r--;
            if(now.r==now.x-1)  Delete(j);
            else
            {
                if(sum[now.r]==1)  len--;
                sum[now.r]--,q[++top]=j;
            }
        }
        ans=ans+(lastlen+len)/2;
        for(int j=head,k;triangle[j].y<=i&&j<=n;j=next[j])
            if(i==triangle[j].y)
            {
                for(k=1;k<=top;k++)
                {
                    if(mark[q[k]]==falsecontinue;
                    if(triangle[q[k]]>triangle[j])
                    {
                        Delete(j);
                        break;
                    }
                    if(triangle[j]>triangle[q[k]])
                    {
                        Delete(q[k]);
                        for(int r=triangle[q[k]].l;r<triangle[q[k]].r;r++)
                        {
                            if(sum[r]==1)  len--;
                            sum[r]--;
                        }
                    }
                }
                if(k<=top)  continue;
                for(int k=triangle[j].l;k<triangle[j].r;k++)
                {
                    if(sum[k]==0)  len++;
                    sum[k]++;
                }
            }
    }
}
int main()
{
    read();
    work();
    printf("%.1lf\n",ans);
    return 0;
}


  评论这张
 
阅读(492)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017