hdu 3642 Get The Treasury (三维的扫描线)[通俗易懂]

hdu 3642 Get The Treasury (三维的扫描线)

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

题目大意:

给出N个立方体。

求一个三维空间中被包围三次的空间的体积之和。

思路分析:

发现Z的范围非常小。那么我们能够枚举Z轴,然后对 x y做扫描线。

并且不用枚举全部的Z ,仅仅须要将Z离散化之后枚举。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 2222
#define debug puts("fuck!")
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
typedef long long LL;
using namespace std;

inline void scanf_(int &num){
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-'){
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}

struct node
{
    int x1,y1,z1;
    int x2,y2,z2;
    void scan()
    {
        scanf_(x1);
        scanf_(y1);
        scanf_(z1);
        scanf_(x2);
        scanf_(y2);
        scanf_(z2);
    }
}cube[maxn];

struct line
{
    int s,e,h,type;
    bool operator < (const line &cmp)const
    {
        return h<cmp.h;
    }
}scline[maxn<<1];

int len[maxn<<2][4];
int cov[maxn<<2];
int x[maxn];
int z[maxn];
int cntx,cntz,n;

void init()
{
    cntx=cntz=0;
}

void pushup(int num,int s,int e)
{
        if(cov[num]>=3)
        {
            len[num][3]=len[num][0];
            len[num][1]=len[num][2]=0;
        }
        else if(cov[num]==2)
        {
            if(s==e)
            {
                len[num][1]=len[num][3]=0;
                len[num][2]=len[num][0];
            }
            else
            {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]
                            +len[num<<1][1]+len[num<<1|1][1];
                len[num][2]=len[num][0]-len[num][3];
                len[num][1]=0;
            }
        }
        else if(cov[num]==1)
        {
            if(s==e)
            {
                len[num][1]=len[num][0];
                len[num][2]=len[num][3]=0;
            }
            else {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2];
                len[num][2]=len[num<<1][1]+len[num<<1|1][1];
                len[num][1]=len[num][0]-len[num][2]-len[num][3];
            }
        }
        else
        {
            len[num][3]=len[num<<1][3]+len[num<<1|1][3];
            len[num][2]=len[num<<1][2]+len[num<<1|1][2];
            len[num][1]=len[num<<1][1]+len[num<<1|1][1];
        }
}
void build(int num,int s,int e)
{
    len[num][0]=x[e+1]-x[s];
    len[num][1]=len[num][2]=len[num][3]=0;
    cov[num]=0;

    if(s==e)return;

    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

void update(int num,int s,int e,int l,int r,int val)
{
    if(l<=s && r>=e)
    {
        cov[num]+=val;

        if(cov[num]>=3)
        {
            len[num][3]=len[num][0];
            len[num][1]=len[num][2]=0;
        }
        else if(cov[num]==2)
        {
            if(s==e)
            {
                len[num][1]=len[num][3]=0;
                len[num][2]=len[num][0];
            }
            else
            {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]
                            +len[num<<1][1]+len[num<<1|1][1];
                len[num][2]=len[num][0]-len[num][3];
                len[num][1]=0;
            }
        }
        else if(cov[num]==1)
        {
            if(s==e)
            {
                len[num][1]=len[num][0];
                len[num][2]=len[num][3]=0;
            }
            else {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2];
                len[num][2]=len[num<<1][1]+len[num<<1|1][1];
                len[num][1]=len[num][0]-len[num][2]-len[num][3];
            }
        }
        else
        {
            len[num][3]=len[num<<1][3]+len[num<<1|1][3];
            len[num][2]=len[num<<1][2]+len[num<<1|1][2];
            len[num][1]=len[num<<1][1]+len[num<<1|1][1];
        }
        return ;
    }

    int mid=(s+e)>>1;

    if(l<=mid)update(lson,l,r,val);
    if(r>mid)update(rson,l,r,val);

    pushup(num,s,e);
}

void solve(int kase)
{
    build(1,0,cntx-2);

    LL ans=0;
    for(int i=0;i<cntz-1;i++)
    {
        int cnt=0;

        for(int j=0;j<n;j++)
        {
            if(cube[j].z1<=z[i] && cube[j].z2>z[i])
            {
                scline[cnt].s=cube[j].x1;
                scline[cnt].e=cube[j].x2;
                scline[cnt].h=cube[j].y1;
                scline[cnt++].type=1;

                scline[cnt].s=cube[j].x1;
                scline[cnt].e=cube[j].x2;
                scline[cnt].h=cube[j].y2;
                scline[cnt++].type=-1;
            }
        }
   
        LL area=0;
        sort(scline,scline+cnt);
       
        for(int j=0;j<cnt-1;j++)
        {
            int l=lower_bound(x,x+cntx,scline[j].s)-x;
            int r=lower_bound(x,x+cntx,scline[j].e)-x;
           
            update(1,0,cntx-2,l,r-1,scline[j].type);
            area+=(LL)len[1][3]*(scline[j+1].h-scline[j].h);
            
        }
        int l=lower_bound(x,x+cntx,scline[cnt-1].s)-x;
        int r=lower_bound(x,x+cntx,scline[cnt-1].e)-x;
        update(1,0,cntx-2,l,r-1,scline[cnt-1].type);
        ans+=area*(z[i+1]-z[i]);
    }
    printf("Case %d: %I64d\n",kase,ans);
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        init();

        scanf("%d",&n);

        for(int i=0;i<n;i++)
        {
            cube[i].scan();

            x[cntx++]=cube[i].x1;
            x[cntx++]=cube[i].x2;

            z[cntz++]=cube[i].z1;
            z[cntz++]=cube[i].z2;
        }

        sort(x,x+cntx);
        sort(z,z+cntz);

        cntx=unique(x,x+cntx)-x;
        cntz=unique(z,z+cntz)-z;
      
        solve(cas);
    }
    return 0;
}

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

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

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

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

(0)


相关推荐

  • oracle 导出时报错EXP-00011:table不存在「建议收藏」

    oracle 导出时报错EXP-00011:table不存在

  • 服务器支持p2v,菜鸟必知 实施P2V迁移成功的五大秘诀

    服务器支持p2v,菜鸟必知 实施P2V迁移成功的五大秘诀虚拟服务器迁移工具对操作系统、应用和设置进行镜像复制,并转换成虚拟硬盘文件(适用于MicrosoftHyper-V和CitrixXenServer来说)或者虚拟机磁盘格式文件(适用于VMware)。然后P2V转换工具自动诸如虚拟硬件驱动,并启动虚拟机运转起来。多数P2V迁移直截了当,但也会偶尔发生问题。下面,GregShields将分享五条让P2V迁移成功的技巧。一、注意已安装的OEM系统当…

  • centos7安装python3.7_安装python教程

    centos7安装python3.7_安装python教程文章目录前言环境&组件说明组件用途说明准备阶段安装步骤详细步骤准备安装安装Python异常处理异常信息原因分析处理方法小技巧前言工作需要,服务器不能连接外网,因此需要离线安装。推荐在线安装,参考。环境&组件说明操作系统:CentOSLinuxrelease7.4.1708(Core)操作系统安装包:CentOS-7-x86_64-Minimal-1708.isoPython版本:3.8.5pip版本:20.1.1virtualenv版本:20.4.2组件用途说

  • DHCP协议简述

    DHCP协议简述DHCP(DynamicHostConfigurationProtocol,动态主机配置协议)是一个局域网的网络协议,使用UDP协议工作,主要有两个用途:给内部网络或网络服务供应商自动分配IP地址,给用户或者内部网络管理员作为对所有计算机作中央管理的手段,在RFC2131中有详细的描述。DHCP有3个端口,其中UDP67和UDP68为正常的DHCP服务端口,分别作为DHCPServer…

  • opc服务器网站,OPC 服务器[通俗易懂]

    opc服务器网站,OPC 服务器[通俗易懂]OPC服务器OPC服务器,是指按照OPC基金组织规定的OPC规范群开发的软件驱动。OPC服务器作为中间媒介负责从数据源读取数据再跟另外一端的客户端通信。在OPC客户端/服务器的结构图中,通信的发起端是,也只能是OPC客户端。客户端和服务器的对话是双向的,也就是说,客户端既可以从服务器读出也可以向服务器写入。TOPC基金会定义了四种不同类型的OPC服务器。他们分别是:OPC数据访问服务器…

  • c++面试基本问题_面试结果一般要等几天

    c++面试基本问题_面试结果一般要等几天1.    面向对象的程序设计思想是什么?答:把数据结构和对数据结构进行操作的方法封装形成一个个的对象。 2.    什么是类?答:把一些具有共性的对象归类后形成一个集合,也就是所谓的类。 3.    对象都具有的二方面特征是什么?分别是什么含义?答:对象都具有的特征是:静态特征和动态特征。静态特征是指能描述对象的一些属性;

发表回复

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

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