娱乐 每 日 算 法 挑 战 【第0期，有红包】

[Mr.K 018]

好的！经过一个晚上的商讨，我们的每日算法挑战要和大家见面了！

如标题所示本期是第0期，就是每日算法挑战的公测。下面放上简介！

1 这是什么？

每日算法挑战本质上不就是拿来热版的花招么

每日算法挑战，顾名思义，就是每天会po一道算法相关的题目，来让大家讨论讨论，做一做。当然了，这个每日算法挑战并不是什么ACM之类的算法题，各位就算交了代码也没有用。因此，大家只要说说算法和思路，最多给出伪代码就可以了。伪代码写得也可以随便一点，但是太过耍赖的“伪代码”也是不行的哦！比如这样的伪代码:

1. 输入本题的所有数据；
2. 解题；
3. 输出结果

这样的伪代码说的就太模糊了，有点耍赖。我们约定除了众所周知的少数算法（如排序）之外，伪代码也要由常数时间内就能做完的动作（或自己定义的过程调用）组成。同样地，对于自定义数据结构也尽可能写的清楚一点为好。

如果觉得伪代码要求太复杂了，其实也不用非得写伪代码，只要能说明白算法的大致实现过程也可以。写得详细的可以拿到和伪代码一样的奖励哦！

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。

输出

输出一行，其中有一个整数，表示雕塑需要多少方块。

嗯……这个题是我杜撰的，因此没有预设的正确答案，大家可以畅所欲言。

[Mr.K 018]

1 分钟前, Orochis 说道:

头痛了，是数列题啊，看着就麻烦

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

[Mr.K 018]

25 分钟前, yhz012 说道:

最平凡的情况是如果多面体确定为凸，那么文件内所有点当做顶点，直接用barycentric coordinates（翻译好像叫重心坐标？）

通过求判定点到各顶点距离反过来解线性方程组能得到barycentric coordinates，然后判定坐标的各分量是否在01之间，如果是，则在体内，否则在体外

 

然后对于非凸的情况就可以做分割得到凸多面体来带走了

 

暴力一点的分割凸多面体方案可以是拿出一个三角面，找和该三角面有公用边的另一个三角面（存在性需要证明，不过目测应该是必然存在的）

这两个三角面构成四面体，为凸，同时得到另外2个新三角面，加入到三角面列表

把所有pair遍历之后应该就能把整个几何体给三角化了

感觉这个三角化有点问题，不过已知顶点集（即输入文件），肯定有三角化的算法，翻一下工具书或者面向github编程一下就可以了吧（

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去

而且用质心坐标的话，怎么解决方块的顶点和中心点都在几何体外，但方块本身却要算进去这种情况呢

（请脑补糖葫芦，山楂是方形的，就是MC中的方块，竹签是那个几何体）

四月 8, 2020，由Mr.K 018修改

[Mr.K 018]

4 分钟前, yhz012 说道:

如果按照我robotics的方案就是暴力分小块……直到一般认为不会再有可能插在中间为止，这是暴力解决方案

 

或者考虑求四面体的4个面对立方体的6个面的交线，如果有交线则应当放置方块

这样的话可以把问题规约到已知两个凸几何体，求两几何体是否相交

需要判定

1. 几何体A的顶点是否在几何体B内

2. 几何体B的顶点是否在几何体A内

3. 几何体A的面是否与几何体B的面存在交线

以上三个任何一个为真，则相交

这个方法我觉得可行，总结一下大概的思路：

1. 将STL中的几何体三角化，分割成一个四面体集；

2. 维护一个放置方块集（初始为空），对四面体集的每一个元素：

2.1 确定要判定的四面体涉及哪些方块（可以通过x,y,z三个轴的最小值、最大值来限定）；

2.2 对每个上一步中得出要考虑的方块，进行求交运算，若相交则入方块集合。

3. 输出方块集合的集合大小，结束。

我原先觉得这个问题应该先考虑表面再填充内部，后来发现这个方法好像不需要填充

 

下一个问题是复杂度，因为我们的目的不是非要找四面体而是找出一个凸的部分即可，现在分成基本的四面体的方法分的是否有些碎呢

[Mr.K 018]

17 分钟前, 随性而为 说道:

其实2D中只要知道在哪几个环状图形内就没必要三角化了，只需要知道环状图形的解析式依然可以用y=1，y=2……求出z的各个值，然后(int )z1-(int)z2+1就是每个y上的方格数了，现在蛋疼的就是怎么求出环形图形

 

7 分钟前, yhz012 说道:

求环不难，举例来说现在你有集合S为在z面上的所有截取线段集合

circleList = []
while not S[i].isEmpty():
  circle = []
  a, b = S[i].pop()
  circle = circle + [a, b]
  c, d = None, None
  while c != a and d != a:
    for line in S[i]:
      c, d = line
      if c == b:
        S = S - {line}
        circle = circle + [d]
        b = c
      elif d == b:
        S = S - {line}
        circle = circle + [c]
        b = d
  circleList = circleList + [circle]

唯一可能出现的问题是有可能存在类似于“8”这样的环，不过这个在之后再判定一下就好了

关于这个，我突然发现我编题的时候没有考虑STL本身是空心的情况

如果要求STL的空心搭出来还是空心（挤没了的不算）的话，平面截出来就会有大环套小环的问题。考虑在线段集里记录每个线段的法向？

[Mr.K 018]

12 分钟前, inuisanaa 说道:

这真的和mc有关系吗，每个字都看得懂，连起来就看不懂了

编程题一般都是题文无关（笑

[Mr.K 018]

1 小时前, 随性而为 说道:

针对这个问题可以有这么一个解决方法：输入数据者在输入数据时可以额外输入哪几个三角面能构成封闭空间，这样可以缩小判断范围，且结果一定是较为准确的

这个的话，原本的STL文件中三角面的存储是有序的（遵循右手法则），可以提供一些关于法向的信息（遗憾的是，本题中不一定这么存储www），然而没有哪些三角面可以构成封闭空间的相关信息

……而且我觉得这个信息的输入是件非常可怕的事情啊，一个几何体的三角面是很多的