斯伦贝谢软件笔经
一道斯伦贝谢软件笔试题
软件, 笔试, 斯伦贝
每个公司的软件题目应该都是其在实际工作当中会遇到的问题，这道斯伦贝谢的算法题我猜测应该也是如此。题目是09届毕业生招聘时出的，如下：
现在一个广场上有一些木桩，可以知道这些木桩的坐标。给你一根很长的绳子，绕成一圈，将所有木桩都绕在里面。之后收紧绳子，直到其紧绷。此时有木桩与绳子接触，另外一些木桩则是在绳子绕成的圈的内部。 我们将与绳子接触的木桩称作顶点，请编写程序，求出这些木桩中的顶点。
这道题目其实不难，诸位读者可以思考一下，再看我给的解决方案。另外提醒一下，木桩的坐标是人定的`，我们可以将木桩的坐标统一定在第一象限。
以下是这个问题的解答，我只给出算法大体流程，但不给出具体代码。
我们的输入是一个数组，这个数组中包含所有木桩的坐标，即一个POINT。
第一步，找出这些点中，位于最下方，即Y坐标值最小的点，我们称之为木桩A
我们以A点作为基准点进行下一步分析。找出逆时针方向的下一个顶点。这个顶点的寻找方向，必然是先找右上方，如果右上方没有点，则找左上方。
在右上方，下一个顶点必然是与A相连，斜率最小的点。如果右上方没有点，那么我们需要从左上方查找斜率也是最小的一个点。这一点读者可以在纸上画图查证。
按照这种方法，我们很容易找到逆时针的下一个点，我们称之为B点，现在从B点查找B点的逆时针下一个顶点。对于B点来说，我们也需要先查找右上方，如果右上方没有木桩，则查找左上方，左上方没有，则需要查找左下方，如果左下方没有，那就需要查找右下方。按照此次序依次查找。
对于右上方有木桩的情形，我们需要找到与B点相连斜率最小的木桩。
右上方无木桩，左上方有木桩的情形，我们需要查找左上方中，与B相连斜率最小的木桩。
对于左下方的情形，我们需要查找与B相连斜率最小的木桩。
对于右下方的情形，我们需要查找与B相连斜率最小的木桩。
虽然都是查找斜率最小，但我们需要依次比较四种情况，而不能混在一起查找。
按照这种方法，我们可以找到C点。
重复由B找到C的步骤，我们可以找到C的逆时针下一个顶点，依次查找，则可以找出所有顶点。这里还需要注意一点，我们需要保存上一次的斜率，本次查找时的斜率必须比上一次查找时的斜率大，或者本次查找的下一个顶点的位置，位于四个方位中的下一个方位。
这个方法很简单，但效率很低，每次查找，都需要计算出当前顶点与其他所有点的斜率，并进行分类排序比较。但目前我只想到这一种方法，如果谁有更好的方法，欢迎给我留言
【斯伦贝谢软件笔经】相关文章：
锡伯族贝伦舞种类10-06
锡伯族贝伦舞的种类及介绍10-05
桂林银行笔试题笔经10-21
招商银行实习生招聘笔经面经12-15
逻辑历史方法考虑下的贝叶斯主义探析论文07-11
劳伦茨·冯·斯泰因的社会—国家思想10-12
贝姓起源介绍01-16
浅析基于贝叶斯网络和CRB的汽车故障诊断系统研究论文06-16
伦斯勒理工学院读电气工程硕士的申请条件06-23
眼线笔类型-如何挑选眼线笔11-09