Mr.K 018

关于这个，我突然发现我编题的时候没有考虑STL本身是空心的情况 如果要求STL的空心搭出来还是空心（挤没了的不算）的话，平面截出来就会有大环套小环的问题。考虑在线段集里记录每个线段的法向？

这个方法我觉得可行，总结一下大概的思路： 1. 将STL中的几何体三角化，分割成一个四面体集； 2. 维护一个放置方块集（初始为空），对四面体集的每一个元素： 2.1 确定要判定的四面体涉及哪些方块（可以通过x,y,z三个轴的最小值、最大值来限定）； 2.2 对每个上一步中得出要考虑的方块，进行求交运算，若相交则入方块集合。 3. 输出方块集合的集合大小，结束。 我原先觉得这个问题应该先考虑表面再填充内部，后来发现这个方法好像不需要填充 下一个问题是复杂度，因为我们的目的不是非要找四面体而是找出一个凸的部分即可，现在分成基本的四面体的方法分的是否有些碎呢

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去 而且用质心坐标的话，怎么解决方块的顶点和中心点都在几何体外，但方块本身却要算进去这种情况呢 （请脑补糖葫芦，山楂是方形的，就是MC中的方块，竹签是那个几何体）

这个题其实是个图形学相关的题，一时兴起就出了这么一道（笑

好，第0期发了！ https://sstm.moe/topic/252752-每-日-算-法-挑-战-【第0期，有红包】/ 今天这个问题是个图形学的问题，我一个小时之内想出来的（ 有一说一 我觉得应该有现成算法，但我没有查2333

好的！经过一个晚上的商讨，我们的每日算法挑战要和大家见面了！ 如标题所示本期是第0期，就是每日算法挑战的公测。下面放上简介！ 1 这是什么？ 每日算法挑战本质上不就是拿来热版的花招么 每日算法挑战，顾名思义，就是每天会po一道算法相关的题目，来让大家讨论讨论，做一做。当然了，这个每日算法挑战并不是什么ACM之类的算法题，各位就算交了代码也没有用。因此，大家只要说说算法和思路，最多给出伪代码就可以了。伪代码写得也可以随便一点，但是太过耍赖的“伪代码”也是不行的哦！比如这样的伪代码: 输入本题的所有数据； 解题； 输出结果 这样的伪代码说的就太模糊了，有点耍赖。我们约定除了众所周知的少数算法（如排序）之外，伪代码也要由常数时间内就能做完的动作（或自己定义的过程调用）组成。同样地，对于自定义数据结构也尽可能写的清楚一点为好。 如果觉得伪代码要求太复杂了，其实也不用非得写伪代码，只要能说明白算法的大致实现过程也可以。写得详细的可以拿到和伪代码一样的奖励哦！ 2 有奖励吗！ 有啊，当然有了！我们欢迎所有形式的讨论，尤其会对这样的贴子发放奖励： 首先给出了正确答案（或者相对本题可以接受的答案）的，可以拿到最多的奖励！ 虽然不是首先给出答案，但是有一些新内容的（比如新方法啊，复杂度等等的讨论啊，算法思路的说明啊，以及正确性证明等等）； 参与讨论，有一些新颖的见解或者指出了其他人答案的bug的。 顺带一提，三种奖励可以叠加！ 今天作为公测，我先放出来一道我随便杜撰的题吧! 第0期 我的世界 K想要在MC里搭一个雕塑。他手头有一个STL文件，里面保存了这个雕塑的样子。 题目中为了简化，认为STL文件由若干三角面组成，每个三角面由九个实数组成，前三个、第4-6个和第7-9个实数分别定义了三角面的三个顶点。可以认为每个STL文件中的各个三角面能围成一个封闭的几何体。 我们规定，对于每个MC中的方块区域，只要三角面穿过了这个区域，就要在那里搭上方块，并且这个雕塑是实心的，即几何体的内部也要填上方块。 K在搭建雕塑之前，首先要知道他要准备多少个方块，来计划挖矿（指给苦力ABCDE等人安排挖矿任务）。现在他想问问你，修雕塑要多少方块呢？ 输入 第一行是一个整数n，表示这个STL文件中的三角面个数。 接下来有n行，每行有9个实数，分别表示三角面中的三个顶点，顺序是X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3。 输出 输出一行，其中有一个整数，表示雕塑需要多少方块。 嗯……这个题是我杜撰的，因此没有预设的正确答案，大家可以畅所欲言。

@萨卡 诶，你也是萨卡

emmm说起来有点不好意思，这两天现实中比较肝，那个坑好几天没怎么动了

好的，我看看今天下午弄一下

@萨卡 萨卡中之人K桑可能性微存？

关于这个问题，我有很明确的答复：这个活动是面向所有人的，以算法交流为主，重点在于如何解决问题，而不是编制没有bug的程序，所以我希望合格的标准能尽可能放开一些。 只不过伪代码肯定不能瞎写对不对（ 关于您提出的这一条规则，实际上是在数据定义方面做的一点注解。实际上可能不会明确地写给大家看。这条规则实际上是说，遇到数据定义中有歧义的地方，按照C语言中struct的处理方法处理。大家读代码的时候如果能看懂是怎么回事或者有注明，就用不上这条规则了。

确实，汇编是真的可怕

我有个临时的想法，还不太成熟。 首先我们不希望参加者提交代码，只需要伪代码即可。这个是大的方面。 考虑到伪代码和文字描述的模糊性，有必要提出几点这里使用的伪代码/文字描述规范，不满足规范的视为思路说明，而非伪代码。我目前想到了如下几点： 文字描述必须包含输入、处理和输出过程，不能假定数据在开始时就已经输入完毕，存储在内存中； 算法的每一步，要么是常数时间内可以完成的动作，要么是众所周知的方法（如排序、最短路等），要么是调用在同一段伪代码中定义的其他方法。循环和方法定义的执行体不视为一步，而是当作多步处理，但其中的每一步仍需满足本条的规范。 要对使用的数据结构有明确的定义。数据结构中要引用其他数据结构的，可以使用指针（如Node* next = nullptr），若做了相应说明，也可以使用引用（如Node next = Null）。但是若没有做说明，则默认内层数据结构是外层数据结构的一个字段，访存时可直接通过外层数据结构的地址和偏移量来访问内层数据结构的成员。默认整数是32位的，实数是64位的，指针是32位的，除特殊说明外字符是单字节的ASCII字符。 尽量少bug。我们不是OJ，不要求伪代码完全正确，但也不是对正确性毫无要求。我们能发现或者被其他人指出来有明显/严重的bug的算法，会酌情扣除少量奖励。奖励发放后被指出错误的，不会追回奖励。 奖励方面，我自己拿不出太多节操，同时我想这个虽然有比赛的成分，但是主要目的还是激发活跃性。因此奖励可能不会太多，就是意思意思。所以可不可以这样： 首先给出可接受答案的，受上赏； 并非首先给出可接受答案，但是给出了新的内容，如算法细节、另一种方法（这个应该不太常见）、更详细的说明、证明等等，受中赏； 参与讨论，给出了有价值的想法以及提出解答中的bug的，受下赏。 非规范的伪代码（即“思路说明”）按详细程度酌情给奖励，最高可以给到相当于一段伪代码的奖励。同时考虑若干加分项： 对算法及其思路进行了较详细解释说明的，如动态规划问题解释清楚动归的目标和状态转移函数； 计算了算法的时空复杂度的。整数和实数的四则运算可以认为能在常数时间内完成，高精度数除外； 对于一些特殊算法（如贪心和剪枝等），证明了正确性的。 @ZERC @inuisanaa @随性而为 @NianRuoshui @魍魉QAQ @提辖 讨论一下，六位的看法是？

其实也没打算是编程，只是算法

要不然让参与者给伪代码？ 给出算法的伪代码表示总比编出能跑的程序简单点

采用参与者提交程序代码的方法的话也不是不行，这种方案就是我初始化一个虚拟机来跑提交的代码，然后构造出一些数据来测的样子。 虚拟机我有，要写一个东西来自动化输入输出并且测量程序用时，而且我也没想好怎么测内存使用 老实说我不喜欢这个方案因为这样有点本末倒置（大家又不是人均ACM，其实我也不打ACM的），大家负担也重咱们负担也重。我要是看到一个让我编程的挑战肯定直接跑路，不会像数学挑战那样坐下来做题的，因为编程时间挺不可控的

说正经的 题目有了，形式呢？ 总不能我把底下所有人写的程序一个一个跑一遍我们学校OJ吧，何况有的题早就关了，就剩下题面

好的，我数了数光前些年校赛和新生赛题目就有三四十道，每天一道就是一个月，一个月的时间三次元板块复兴有望啊（

我刚刚搞到了我们学校以前的校赛和新生赛题目 网址是我们学校的moodle平台，所以就不贴了 我或许能找到校友（不是

SSTM virtual judge 我看行

对呀，所以说上课学会了py的语法距离真正的会py我觉得有点距离

py：都 给 👴 爬

这个确实 一般大学C语言是必修，py是选修而且教的非常浅，光会py本身没有用过库那不就是不会py么（ 计算机或软件相关的系除外，这种人主流不太奇怪的语言上手都比较快

啊 不会是要论坛搭OJ或者自己运行程序吧？ 而且要测的话，很多时候拿得到题拿不到数据，除非我们把代码拷出来送到相应OJ平台去测——但那样的话答题人就不能先把程序跑通了再提交么 所以我觉得具体的细节还得考虑一下

要不然找找各个大学计院的算法新生赛？那些题一般都不难