一道编程难题星际迷航……

加拿大家园论坛

一道编程难题星际迷航……

原文链接：https://forum.iask.ca/threads/865775/

gongbao : 2019-01-19#1

C#测试题，小弟不才，请坛内高手指点一二。谢谢大家！！

j0n6dj2y2w : 2019-01-19#2

这么简单都不会？哈哈哈哈 :wdb6:

帮忙顶贴增加人汽。

gongbao : 2019-01-19#3

j0n6dj2y2w 说:
这么简单都不会？哈哈哈哈

帮忙顶贴增加人汽。

鸡哥，你会你说嘛

gongbao : 2019-01-19#4

coplanar

j0n6dj2y2w : 2019-01-19#5

gongbao 说:
鸡哥，你会你说嘛

先谈谈报酬。

gongbao : 2019-01-19#6

j0n6dj2y2w 说:
先谈谈报酬。

谈钱伤感情，怎么你个好兄弟也要钱唉

fierysteed : 2019-01-19#7

1. 找出所有3点组合，要求这三点不在一个直线上。List<Plane>
2. 如果其他点不在这个面一侧，而是两侧，那么这个面不用，过滤掉。 List<Plane>
3. 找出离这个面最远点的距离 Height
4。所有点投影在这个面上，然后找最小圆
https://en.wikipedia.org/wiki/Smallest-circle_problem
5. height * Area。
6. 找最小

感觉这道题我觉得比较啰嗦，需要的几何公式比较复杂。即便很努力做，也要一天啊。
我抛转引玉。等更好解法吧。

gongbao : 2019-01-19#8

fierysteed 说:
1. 找出所有3点组合，要求这三点不在一个直线上。List<Plane>
2. 如果其他点不在这个面一侧，而是两侧，那么这个面不用，过滤掉。 List<Plane>
3. 找出离这个面最远点的距离 Height
4。所有点投影在这个面上，然后找最小圆
https://en.wikipedia.org/wiki/Smallest-circle_problem
5. height * Area。
6. 找最小

感觉这道题我觉得比较啰嗦，需要的几何公式比较复杂。即便很努力做，也要一天啊。
我抛转引玉。等更好解法吧。

谢谢，感觉有点思路了。

第四点，应该是所有点投影在这个面上，求那个圆能包含所有点投影点吧？

另外，根据第2点，这可能有多个符合要求的平面，还得比较不同平面上能弄出的圆形底面积 * 对应的最大高度？

gongbao : 2019-01-19#9

我现在感觉其实这是一道求极限问题啊，如果能归纳出公式 y= ax^n + bx^n-1 + cx^n-2 + ... + C的形式，再求极限最小值？唉，好像不对，应该是右边有3个变量x, y, z分别代表三维坐标，可能x,y,z直接有些联系，能化简成两个变量？

woodenwang : 2019-01-19#10

应该就是这个思路了

woodenwang : 2019-01-19#11

gongbao 说:
谢谢，感觉有点思路了。

第四点，应该是所有点投影在这个面上，求那个圆能包含所有点投影点吧？

另外，根据第2点，这可能有多个符合要求的平面，还得比较不同平面上能弄出的圆形底面积 * 对应的最大高度？

要比较所有可能平面

gongbao : 2019-01-19#12

woodenwang 说:
要比较所有可能平面

唉那又要搞什么动态规划了？我忘光了啊

gongbao : 2019-01-19#13

woodenwang 说:
应该就是这个思路了

就是火龙驹的思路嘛？

woodenwang : 2019-01-19#14

gongbao 说:
就是火龙驹的思路嘛？

是的,这个用不到动态规划,在第二步确定所有可能平面后,遍历一遍那个集合找最小值即可

woodenwang : 2019-01-19#15

仼选三点先求平面法向量,有法向量就有平面方程了a=(y1−y0)(z2−z0)−(y2−y0)(z1−z0)b=(x2−x0)(z1−z0)−(x1−x0)(z2−z0)c=(x1−x0)(y2−y0)−(x2−x0)(y1−y0)

woodenwang : 2019-01-19#16

计算点到平面投影坐标https://www.cnblogs.com/nobodyzhou/p/6145030.html

woodenwang : 2019-01-19#17

判断两点是否在平面同侧https://zhidao.baidu.com/question/2143247418303562468.html

邪恶联盟 : 2019-01-19#18

1. 找出三点的外切圆，所有的。
2. 如果这个外切圆可以使所有点都在一侧，而且的形成的圆柱可以包围所以点，就求圆柱的高(法向最远点)。
3. 找到体积最小的。
需要较高的图形学基础。

woodenwang : 2019-01-19#19

最小圆覆盖算法https://www.cnblogs.com/tjsudys/p/4464481.html，这个是二维的,三维平面稍修改即可

woodenwang : 2019-01-19#20

这题目对立体几何知识要求多过编程本身

woodenwang : 2019-01-19#21

宫保是又在面试了？

woodenwang : 2019-01-19#22

咋感觉瑞典企业的面试题总是喜欢把数学和算法混一起呀，记得你上次面试有一题也是这样类型

woodenwang : 2019-01-19#23

宫保加油,我再去睡会 :wdb6:

gongbao : 2019-01-19#24

woodenwang 说:
是的,这个用不到动态规划,在第二步确定所有可能平面后,遍历一遍那个集合找最小值即可

woodenwang 说:
仼选三点先求平面法向量,有法向量就有平面方程了a=(y1−y0)(z2−z0)−(y2−y0)(z1−z0)b=(x2−x0)(z1−z0)−(x1−x0)(z2−z0)c=(x1−x0)(y2−y0)−(x2−x0)(y1−y0)

woodenwang 说:
计算点到平面投影坐标https://www.cnblogs.com/nobodyzhou/p/6145030.html

woodenwang 说:
判断两点是否在平面同侧https://zhidao.baidu.com/question/2143247418303562468.html

woodenwang 说:
最小圆覆盖算法https://www.cnblogs.com/tjsudys/p/4464481.html，这个是二维的,三维平面稍修改即可

谢谢！！！
总结一下，然后照着撸！！！

gongbao : 2019-01-19#25

woodenwang 说:
宫保是又在面试了？

woodenwang 说:
咋感觉瑞典企业的面试题总是喜欢把数学和算法混一起呀，记得你上次面试有一题也是这样类型

woodenwang 说:
宫保加油,我再去睡会

是的，我做好几个测试了，其他的是人际关系，智商，逻辑测试，就这个是编程测试。

这都是人力资源公司瞎出的题，出题人自己并不懂。

你睡吧，我刚刚下午睡醒

gongbao : 2019-01-19#26

@woodenwang
下面是我找到的一些链接，你看能用上不？

http://paulbourke.net/geometry/circlesphere/
http://csharphelper.com/blog/2014/08/find-a-minimal-bounding-circle-of-a-set-of-points-in-c/
http://csharphelper.com/blog/2014/07/find-the-convex-hull-of-a-set-of-points-in-c/
https://www.staff.uni-mainz.de/schoemer/publications/ALGO00.pdf
https://answers.unity.com/questions/836915/smallest-bounding-sphere.html
https://math.stackexchange.com/questions/127569/optimization-with-cylinder
https://www.mathopenref.com/cylindervolume.html

gongbao : 2019-01-19#27

woodenwang 说:
是的,这个用不到动态规划,在第二步确定所有可能平面后,遍历一遍那个集合找最小值即可

这样可以吗？体积V = (pi)* R^2 * h，底面积虽小，h可能会很大，虽然h是线性的，但是无法证明一定就比R^2小啊

woodenwang : 2019-01-19#28

题目中说了不会有4个点共面的情况，所以你首先找出所有3点形成的面，然后将不是所有点在面一侧的面去除掉，就会得到一个符合条件的面的集合，对集合里的每个面，都求出其余所有点映射到这个面后的最小圆的R，以及最远距离点的H，这样就可以求得以这个面为底的圆柱的体积。比较这些求出的体积，得一个最小值就是解了。

gongbao : 2019-01-19#29

woodenwang 说:
题目中说了不会有4个点共面的情况，所以你首先找出所有3点形成的面，然后将不是所有点在面一侧的面去除掉，就会得到一个符合条件的面的集合，对集合里的每个面，都求出其余所有点映射到这个面后的最小圆的R，以及最远距离点的H，这样就可以求得以这个面为底的圆柱的体积。比较这些求出的体积，得一个最小值就是解了。

对呀，我就是这个意思。单独比较底面积即半径不够，应该是比较R^2 * h吧？

woodenwang : 2019-01-19#30

gongbao 说:
对呀，我就是这个意思。单独比较底面积即半径不够，应该是比较R^2 * h吧？

是的

gongbao : 2019-01-19#31

woodenwang 说:
是的

好的，多谢！

今天踢球了，好困。明天再弄。

fieldmarshal : 2019-01-19#32

这种数学题最操蛋，面试的自己都未必会。很多年前我也做过一次，费脑子，进去以后我以为大家都是大牛，后来发现几年中只有我完整给了所有程序，他大爷的

lee2000n : 2019-01-19#33

敢問這個編程題是你工作面試題還是學生的考試題？是面試題的話是軟件編程員還是網頁編程員？

gongbao : 2019-01-20#34

fieldmarshal 说:
这种数学题最操蛋，面试的自己都未必会。很多年前我也做过一次，费脑子，进去以后我以为大家都是大牛，后来发现几年中只有我完整给了所有程序，他大爷的

HR出的题她们不懂

gongbao : 2019-01-20#35

lee2000n 说:
敢問這個編程題是你工作面試題還是學生的考試題？是面試題的話是軟件編程員還是網頁編程員？

工作
什么工作不知道，有区别吗？

gongbao : 2019-01-20#36

这个题好恶心啊，麻烦得要死，计算烦杂的很

lee2000n : 2019-01-20#37

gongbao 说:
工作
什么工作不知道，有区别吗？

非常有區別啊，你申請的工作不知道工作title和工作內容？

gongbao : 2019-01-20#38

lee2000n 说:
非常有區別啊，你申請的工作不知道工作title和工作內容？

桌面软件网页开发都是程序员面试阶段只能考察一下算法呗

现在开发桌面软件的工作很少啊都是手机app或web

lee2000n : 2019-01-20#39

gongbao 说:
桌面软件网页开发都是程序员面试阶段只能考察一下算法呗

现在开发桌面软件的工作很少啊都是手机app或web

我面試的網頁編程工作都沒這個算法的面試題哦

gongbao : 2019-01-20#40

lee2000n 说:
我面試的網頁編程工作都沒這個算法的面試題哦

那你幸运呗

我这边公司不管三七二十一先给一堆题过了才有机会下一步

lee2000n : 2019-01-20#41

gongbao 说:
那你幸运呗

我这边公司不管三七二十一先给一堆题过了才有机会下一步

你在多倫多還是溫哥華？

加拿大家园论坛一道编程难题 星际迷航……

原文链接：https://forum.iask.ca/threads/865775/

加拿大家园论坛

一道编程难题星际迷航……