bzoj 3225: [Sdoi2008] 立方体覆盖 题解「建议收藏」

bzoj 3225: [Sdoi2008] 立方体覆盖 题解

大家好,又见面了,我是全栈君。

【原题】

3225: [Sdoi2008]立方体覆盖

Time Limit: 2 Sec  
Memory Limit: 128 MB


Submit: 51  
Solved: 36

[
Submit][
Status]

Description

  A君近日为准备省队选拔。特意进行了数据结构的专项训练。训练过程中就遇到了“矩形面积并”这道经典问题。即:给出N个各边与坐标轴平行(垂直)的矩形,求矩形覆盖的面积之和。

A君按纵坐标建立线段树后按横坐标扫描计算。轻易AC了这道题,时间复杂度为O(NlogN)。

  为了强化训练。A君将问题推广到三维空间中,即:给出N个各棱与坐标轴平行(垂直)的立方体,求立方体覆盖的体积之和。为了简化问题,令立方体均退化为正立方体,用四元组(x, y, z, r)表示一个立方体,当中x, y, z为立方体的中心点坐标。r为中心点到立方体各个面的距离(即立方体高的一半)。
  这次可难住了A君。仅仅好请你——未来的金牌——来帮助他了。
 

Input

  第一行是一个正整数N。
  下面N行每行四个整数x, y, z, r,由空格隔开。

 

Output

 
  共一个数,即覆盖的整体积。

 

Sample Input

3
0 0 0 3
1 –1 0 1
19 3 5 6

Sample Output

1944

HINT

对于 100% 的数据。1≤N≤100

对于 100% 的数据,-1000≤x, y, z≤1000。1≤r≤200

【做法1】n=100?暴力能过吗?暴力离散、统计。。极限效率大概是:200^3*100。并且去重能够提高一点效率。

【代码1】

#include<cstdio>
#include<algorithm>
#define N 105
#define M 210
using namespace std;
int n,X,Y,Z,R,hx,hy,hz,tx,ty,tz,i,j,k,p,flag,ans;
int x1[N],x2[N],y1[N],y2[N],z1[N],z2[N],xx[M],yy[M],zz[M],x[M],y[M],z[M];
int main()
{
  scanf("%d",&n);
  for (i=1;i<=n;i++)
  {
    scanf("%d%d%d%d",&X,&Y,&Z,&R);
    x1[i]=X-R;x2[i]=X+R;
    y1[i]=Y-R;y2[i]=Y+R;
    z1[i]=Z-R;z2[i]=Z+R;
  }
  for (i=1;i<=n;i++)
  {
    xx[++hx]=x1[i];xx[++hx]=x2[i];
    yy[++hy]=y1[i];yy[++hy]=y2[i];
    zz[++hz]=z1[i];zz[++hz]=z2[i];
  }
  sort(xx+1,xx+hx+1);xx[0]=xx[1]-1;
  sort(yy+1,yy+hy+1);yy[0]=yy[1]-1;
  sort(zz+1,zz+hz+1);zz[0]=zz[1]-1;
  for (i=1;i<=hx;i++) if (xx[i]!=xx[i-1]) x[++tx]=xx[i];
  for (i=1;i<=hy;i++) if (yy[i]!=yy[i-1]) y[++ty]=yy[i];
  for (i=1;i<=hz;i++) if (zz[i]!=zz[i-1]) z[++tz]=zz[i];
  for (i=1;i<tx;i++)
    for (j=1;j<ty;j++)
      for (k=1;k<tz;k++)
      {
        flag=1;
        for (p=1;p<=n&&flag;p++)
          if (x1[p]<=x[i]&&x[i+1]<=x2[p]&&y1[p]<=y[j]&&y[j+1]<=y2[p]&&z1[p]<=z[k]&&z[k+1]<=z2[p])
            flag=0;
        if (!flag) ans+=(x[i+1]-x[i])*(y[j+1]-y[j])*(z[k+1]-z[k]);
      }
  printf("%d",ans);
  return 0;
}

【分析2】那么我们就乖乖地写标算。显然。直接线段树套线段树有点虚啊。

于是我先枚举离散后的H,再次基础上建立满足条件的x和y。这样转化成了经典的NLOG(N)的矩形面积并了。

利用扫描线的思想。把每一条竖边取出并按x从左到右快排。然后扫描。假设一条边是始边,把线段树中的y1–y2加1。否则把y1–y2减1。然后对于每个不同的x,把线段树中覆盖层数大于1的个数*(x[i+1]-x[i])。

这个线段树的细节非常多。比方线段树建立是l~mid,mid~r。然后叶子节点是l~l+1。

【代码2】

#include<cstdio>
#include<algorithm>
#define N 105
#define A 1200
#define M 210
using namespace std;
struct Tree{int l,r,sum,cover;}a[M*2*16];
struct arr
{
  int x,l,r,p;
  friend  bool operator < (const arr &a,const arr &b)
  {
    if (a.x!=b.x) return a.x<b.x;
    return !a.p&&b.p;
  }
}E[M*2];
int n,X,Y,Z,r,hz,tz,L,R,i,j,k,opt,h,hy,ty,p,tot,flag,temp,H,W,ans;
int x1[N],x2[N],y1[N],y2[N],z1[N],z2[N],zz[M],z[M],yy[M],y[M],pre[2405];
void build(int k,int l,int r)
{
  a[k].l=l;a[k].r=r;a[k].sum=0;a[k].cover=0;
  if (l+1==r||l==r) return;int mid=(l+r)>>1;
  build(k<<1,l,mid);
  build(k<<1|1,mid,r);
}
void Cover_Add(int k)
{
  if (L<=a[k].l&&a[k].r<=R)
  {
    if (!opt) a[k].cover++,a[k].sum=y[a[k].r]-y[a[k].l];
    else if (!(--a[k].cover)) a[k].sum=(a[k].l+1>=a[k].r)?

0:a[k<<1].sum+a[(k<<1)+1].sum; return; } int mid=(a[k].l+a[k].r)/2; if (L<mid) Cover_Add(k<<1); if (R>mid) Cover_Add(k<<1|1); if (!a[k].cover) a[k].sum=a[k<<1].sum+a[k<<1|1].sum;}int main(){ scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d%d%d%d",&X,&Y,&Z,&r); x1[i]=X-r;x2[i]=X+r; y1[i]=Y-r;y2[i]=Y+r; z1[i]=Z-r;z2[i]=Z+r; } for (i=1;i<=n;i++) zz[++hz]=z1[i],zz[++hz]=z2[i]; sort(zz+1,zz+hz+1);zz[0]=zz[1]-1; for (i=1;i<=hz;i++) if (zz[i]!=zz[i-1]) z[++tz]=zz[i]; for (k=1;k<tz;k++) { H=z[k+1]-z[k];h=hy=ty=0;temp=tot=0; for (i=1;i<=n;i++) if (z1[i]<=z[k]&&z[k+1]<=z2[i]) { E[++h]=(arr){x1[i],y1[i],y2[i],0}; E[++h]=(arr){x2[i],y1[i],y2[i],1}; yy[++hy]=y1[i];yy[++hy]=y2[i]; } sort(yy+1,yy+hy+1);yy[0]=yy[1]-1; for (i=1;i<=hy;i++) if (yy[i]!=yy[i-1]) y[++ty]=yy[i],pre[yy[i]+A]=++tot; if (!ty) continue; sort(E+1,E+h+1);build(1,1,ty); for (i=1;i<h;i++) { W=E[i+1].x-E[i].x; L=pre[E[i].l+A];R=pre[E[i].r+A];opt=E[i].p; Cover_Add(1); if (E[i].x!=E[i+1].x||i+1==h) temp+=a[1].sum*W; } ans+=temp*H; } printf("%d",ans); return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115620.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java高并发 pdf_Java高并发编程详解 PDF 下载

    java高并发 pdf_Java高并发编程详解 PDF 下载推荐序一推荐序二推荐序三推荐序四前言第一部分多线程基础第1章快速认识线程1.1线程的介绍1.2快速创建并启动一个线程1.3线程的生命周期详解1.4线程的start方法剖析:模板设计模式在Thread中的应用1.5Runnable接口的引入以及策略模式在Thread中的使用1.6本章总结第2章深入理解Thread构造函数2.1线程的命名2.2线程的父子关系2.3Thread与…

  • Laravel数据库操作的三种方式

    Laravel数据库操作的三种方式

    2021年10月24日
  • jetbrains 2021激活码【2021最新】

    (jetbrains 2021激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~23LNPMIJZT-eyJsaWNlbnNlSWQiOi…

  • DELL服务器数据恢复成功案例

    DELL服务器数据恢复成功案例DELLEqualLogicPS6100采用虚拟ISCSISAN阵列,为远程或分支办公室、部门和中小企业存储部署带来企业级功能、智能化、自动化和可靠性。以简化的管理、快速的部署及合理的价格满足了分支办公室和中小企业的存储需求,同时提供全套企业级数据保护和管理功能、可靠的性能、可扩展性和容错功能,是中型企业级存储的起点产品,但某些物理故障或其他操作都可能会对卷或存储造成破坏,因此对系列存储的数…

  • docker-compose 集群_基于hadoop的集群搭建

    docker-compose 集群_基于hadoop的集群搭建前言实际工作中我们部署一个应用,一般不仅仅只有一个容器,可能会涉及到多个,比如用到数据库,中间件MQ,web前端和后端服务,等多个容器。我们如果一个个去启动应用,当项目非常多时,就很难记住了,所有

  • 人工势场法matlab讲解_【机器人路径规划】人工势场法

    人工势场法matlab讲解_【机器人路径规划】人工势场法阅读本文需要的基础知识为:理解机器人的构型空间。建议阅读:机器人运动规划中的Cspace怎样理解?为什么不直接在笛卡尔坐标系下运算呢?本文的实现程序与使用说明见我的学习工具箱:小明工坊:【个人开源】机器人运动规划学习工具箱使用说明基本原理1.概述我们打两个比方来说明人工势场法的作用机理。首先,我们把构型空间比作一个电势场平面,机器人(的当前构型)比作空间中一点。如果让机器人的起点和障碍物带正…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号