例题 6-18 雕塑(Sculpture,ACM/ICPC NWERC 2008,UVa12171)

原题链接:https://vjudge.net/problem/UVA-12171
分类:图
备注:离散化;floodfill

紫书思路:利用离散化把三维图缩小,用floodfill求出外围空气体积和内表面积,总体积减去空气体积即所求体积,内表面积即所求表面积。

离散化知识参考:https://blog.csdn.net/tlonline/article/details/46964693
对应练习题:https://vijos.org/p/1056

参考题解博文:https://blog.csdn.net/qq_40738840/article/details/104403108
感谢该文章让我懂了离散化是怎么样实际来使用的,好歹可以AC上面那个练习题了。下述代码也是借鉴了大半。

代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int dir[6][3] = { {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1}, {0,0,-1} };
const int maxn = 50 + 5;
const int maxp = 1001;
int t, n;
int sx[maxn], sy[maxn], sz[maxn], ex[maxn], ey[maxn], ez[maxn];
int dx[maxn * 2], dy[maxn * 2], dz[maxn * 2], g[maxn * 2][maxn * 2][maxn * 2];
void discretize(int *a, int& len) {
	sort(a, a + len);
	len = unique(a, a + len) - a;
}
int getId(int* a, int len, int val) {
	return lower_bound(a, a + len, val) - a;
}
struct node {
	int x, y, z;
	node(int _x, int _y, int _z) :x(_x), y(_y), z(_z) {}
};
int main(void) {
	scanf("%d", &t);
	while (t--) {
		memset(g, 0, sizeof(g));
		scanf("%d", &n);
		dx[0] = dy[0] = dz[0] = 0;
		dx[1] = dy[1] = dz[1] = maxp;
		//相当于率先规定了一个大的空气块,左下角坐标为(0,0,0),沿对应轴长度为1001,1001,1001,总体积就为1001^3
		int lenx = 2, leny = 2, lenz = 2;
		for (int i = 0; i < n; i++) {
			int lx, ly, lz;
			scanf("%d %d %d %d %d %d", &sx[i], &sy[i], &sz[i], &lx, &ly, &lz);
			ex[i] = sx[i] + lx; ey[i] = sy[i] + ly; ez[i] = sz[i] + lz;
			dx[lenx++] = sx[i]; dx[lenx++] = ex[i];
			dy[leny++] = sy[i]; dy[leny++] = ey[i];
			dz[lenz++] = sz[i]; dz[lenz++] = ez[i];
		}
		discretize(dx, lenx); discretize(dy, leny); discretize(dz, lenz);
		for (int i = 0; i < n; i++) {
			int st_x = getId(dx, lenx, sx[i]);
			int ed_x = getId(dx, lenx, ex[i]);
			int st_y = getId(dy, leny, sy[i]);
			int ed_y = getId(dy, leny, ey[i]);
			int st_z = getId(dz, lenz, sz[i]);
			int ed_z = getId(dz, lenz, ez[i]);
			//g[x][y][z]代表x-x+1,y-y+1,z-z+1一整个方块
			for (int i = st_x; i < ed_x; i++)
				for (int j = st_y; j < ed_y; j++)
					for (int k = st_z; k < ed_z; k++) 
						g[i][j][k] = 1;
		}
		int Volum = 0, Area = 0;
		queue<node>Q;
		Q.push(node(0, 0, 0));
		g[0][0][0] = 2;
		while (!Q.empty()) {
			node u = Q.front(); Q.pop();
			Volum += (dx[u.x + 1] - dx[u.x]) * (dy[u.y + 1] - dy[u.y]) * (dz[u.z + 1] - dz[u.z]);
			for (int i = 0; i < 6; i++) {
				int tx = u.x + dir[i][0];
				int ty = u.y + dir[i][1];
				int tz = u.z + dir[i][2];
				if (tx < 0 || ty < 0 || tz < 0 || tx >= lenx - 1 || ty >= leny - 1 || tz >= lenz - 1)continue;
				if (g[tx][ty][tz] == 1) {
					if (dir[i][0] != 0)
						Area += (dy[u.y + 1] - dy[u.y]) * (dz[u.z + 1] - dz[u.z]);
					else if (dir[i][1] != 0)
						Area += (dx[u.x + 1] - dx[u.x]) * (dz[u.z + 1] - dz[u.z]);
					else if (dir[i][2] != 0) 
						Area += (dx[u.x + 1] - dx[u.x]) * (dy[u.y + 1] - dy[u.y]);
				}
				else if (g[tx][ty][tz] == 0) {
					g[tx][ty][tz] = 2;
					Q.push(node(tx, ty, tz));
				}	
			}
		}
		Volum = maxp * maxp * maxp - Volum;
		printf("%d %d\n", Area, Volum);
	}
	return 0;
}

热门文章

暂无图片
编程学习 ·

百天打卡计划第四天-Thread之类的加载过程

类的加载过程 类的加载过程一般分为三个大阶段,加载阶段、连接阶段、初始化阶段。 1加载阶段:主要是负责查找并加载类的二进制数据文件,其实就是class文件。 2连接阶段:连接阶段的工作主要分为三个阶段验证:主要是确保类文件的正确性。 准备:为类的静态变量分配内存,并为…
暂无图片
编程学习 ·

Centos7下redis6.0.5的详细安装步骤

Centos7下redis6.0.5的详细安装步骤: 0、官网浏览,安装wget 1、打开 https://redis.io/download,浏览最新的redis信息。 2、安装wget:执行命令:yum install wget -y 备注:-y的意思是yes 1、wget获得redis安装包 执行: wget http://download.redis.io/releases/redis-6.0…
暂无图片
编程学习 ·

Spring——Bean scope

Spring framework 支持6个范围(scope),其中4个只能在用web-aware时才能使用。当然,你也可以创建自定义范围。singleton : spring默认就是singleton,即在注册该bean的时候,会把这个bean存储到单列bean缓存,以后对该bean的所有的后续请求和引用都会返回缓存中的这一个bean…
暂无图片
编程学习 ·

表单标签「form」+「input」常见用法

表单标签: 表单标签的作用是用于提交数据给服务器的。表单标签的根标签是<form>标签常用的属性:action: 该属性是用于指定提交数据的地址。method: 指定表单的提交方式。get : 默认使用的提交方式。 提交的数据会显示在地址栏上。post : 提交的数据不会显示在地址栏…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

Java Web 第八节 Javascript

这是阿锃总结黑马程序员的第八节的内容&#xff0c;主要是对于JavaScript的相关知识和操作&#xff0c;总结到这里&#xff0c;希望可以帮助到大家&#xff0c;若是大家也想要跟随黑马程序员学习JAVA WEB可以打开我的主页查找第一节的文章&#xff0c;里面有黑马程序员的视频链…
暂无图片
郑州普通话 ·

通用学术英语重点词汇表81-90词

81.substance 释义 n. 物质&#xff0c;材料&#xff1b;实质&#xff1b;主旨&#xff0c;主要内容 例句 Petrol is a volatile substance. 汽油是挥发性物质。 Nothing of any substance was achieved in the meeting. 会议没有取得任何实质性成果。 82.instrument …
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…