你有许多不同高度的杆子，间隔均匀，还有一根绳子穿过杆子的顶端绳子绷得很紧，不会下垂。很明显，绳子不一定会碰到所有杆子的顶端——例如，如果一根杆子比它两边的两根短，那么绳子就永远不会碰到那根杆子。
我们如何找到哪根杆子碰到绳子而哪根没有？
有人告诉我，有一种算法比n平方更快。
（不是家庭作业）
最佳答案
这基本上就是convex hull problem。（多边形顶点是所有极点的顶部，以及第一个和最后一个极点的底部。）链接的维基百科页面给出了几种优于O（n2）的算法最好的似乎是marriage-before-conquest和Chan's algorithm，两者都是O（n log h），其中n是极点的数目（+2），h是绳子实际接触的极点的数目（也是+2）。
实际上，如果极点已经按x坐标排序，Graham scan和Monotone Chain算法是o（n）。