考虑二维平面上的一些点并使用f(x)=ax
函数,其中b=0
。假设一个点是1x1正方形。
现在我们要告诉f(x)
函数和y线之间有多少个点,如下图所示。
黑点有效,白点无效。我们还说,如果满足以下条件,则该点是有效的:
y
轴相交; f(x)
; 如图所示:
假设我们不删除任何要点,也不添加它们,那么我们如何解决呢?除了标准蛮力外,还有其他方法吗?
最佳答案
如果我理解这一权利,则这些点是随机的,并由其坐标给您,并且线也给您。如果真是这样,那么就没有关于点之间任何关系的先验知识,因此您必须按照给定的顺序遍历它们,然后将它们的x坐标与0进行比较,并将它们的y坐标与f(x )。如果某个点通过了支票,则您会增加计数器,否则不会。该算法运行时间为O(n),我高度怀疑如果没有一些有关这些点的额外信息,您可以做得更好。
关于computational-geometry - 某条线上的点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7827558/