斯伦贝谢软件笔试经验

斯伦贝谢软件笔试经验

　　一道斯伦贝谢软件笔试题

　　软件, 笔试, 斯伦贝

　　每个公司的软件题目应该都是其在实际工作当中会遇到的问题，这道斯伦贝谢的算法题我猜测应该也是如此。题目是09届毕业生招聘时出的，如下：

　　现在一个广场上有一些木桩，可以知道这些木桩的坐标。给你一根很长的绳子，绕成一圈，将所有木桩都绕在里面。之后收紧绳子，直到其紧绷。此时有木桩与绳子接触，另外一些木桩则是在绳子绕成的圈的内部。 我们将与绳子接触的木桩称作顶点，请编写程序，求出这些木桩中的顶点。

　　这道题目其实不难，诸位读者可以思考一下，再看我给的解决方案。另外提醒一下，木桩的坐标是人定的，我们可以将木桩的坐标统一定在第一象限。

　　以下是这个问题的解答，我只给出算法大体流程，但不给出具体代码。

　　我们的输入是一个数组，这个数组中包含所有木桩的坐标，即一个POINT。

　　第一步，找出这些点中，位于最下方，即Y坐标值最小的点，我们称之为木桩A

　　我们以A点作为基准点进行下一步分析。找出逆时针方向的下一个顶点。这个顶点的寻找方向，必然是先找右上方，如果右上方没有点，则找左上方。

　　在右上方，下一个顶点必然是与A相连，斜率最小的点。如果右上方没有点，那么我们需要从左上方查找斜率也是最小的一个点。这一点读者可以在纸上画图查证。

　　按照这种方法，我们很容易找到逆时针的下一个点，我们称之为B点，现在从B点查找B点的'逆时针下一个顶点。对于B点来说，我们也需要先查找右上方，如果右上方没有木桩，则查找左上方，左上方没有，则需要查找左下方，如果左下方没有，那就需要查找右下方。按照此次序依次查找。

　　对于右上方有木桩的情形，我们需要找到与B点相连斜率最小的木桩。

　　右上方无木桩，左上方有木桩的情形，我们需要查找左上方中，与B相连斜率最小的木桩。

　　对于左下方的情形，我们需要查找与B相连斜率最小的木桩。

　　对于右下方的情形，我们需要查找与B相连斜率最小的木桩。

　　虽然都是查找斜率最小，但我们需要依次比较四种情况，而不能混在一起查找。

　　按照这种方法，我们可以找到C点。

　　重复由B找到C的步骤，我们可以找到C的逆时针下一个顶点，依次查找，则可以找出所有顶点。这里还需要注意一点，我们需要保存上一次的斜率，本次查找时的斜率必须比上一次查找时的斜率大，或者本次查找的下一个顶点的位置，位于四个方位中的下一个方位。

　　这个方法很简单，但效率很低，每次查找，都需要计算出当前顶点与其他所有点的斜率，并进行分类排序比较。但目前我只想到这一种方法，如果谁有更好的方法，欢迎给我留言 。